Heroku lets you use ClearDB which is a MySQL clone - 100% compatible with MySQL.
As far as the underlying OS goes, it is Linux - but that shouldn't matter to you since your interaction with the servers your application is running on will be limited.
And apparently a basic plan starts at $9 just for the datastore + 9.99 for ClearDB? Meaning that it will cost me 18.99 a month from the get go? Is that how it works?
I know this sounds silly, but where would I even start if I wanted to move my site over to heroku?
As far as the underlying OS goes, it is Linux - but that shouldn't matter to you since your interaction with the servers your application is running on will be limited.