A lot of times I see posts about which hosting providers are great for Rails. I want to give a shout out to Eapps.com. They have been my hosting provider for the past 3 years, they have the best tech support in the hosting business in my opinion. Always willing to help you out.
All Eapps accounts are VPS (Virtual Private Server) and start at $10 running Cent OS (Redhat) Linux. They now have full Rails support. I have been running Rails on my VPS before they officially support since they give you root access and you can install what ever you want.
So if your looking for a hosting provider I recommend giving eApps a look.