Could anyone guide me to a Rails host. Since I am starting off for the first time I am looking at a budget of a around $5/month.
looks like hostingrails has a cheap option in there.
You're budget is pretty low. For that kind of price you're likely to get a shared server that has a set of headaches all it's own. If you can afford $20/mo we've been pretty happy on Slicehost. Another alternative that might work just for timing is heroku.com; they're in beta and I don't think they're charging at the moment.
http://wiki.rubyonrails.com/rails/pages/RailsWebHosts
However, I also HIGHLY recommend Slicehost (www.slicehost.com) if you're willing to go to $20/mo.
Your $5 limit will probably keep you on a shared system. If that's the case, try to find a host who's running mod_rails -- it's brand new, so there may not be anyone, yet.