http://www.couchsurfing.org is similar but free. If you're the social kind (or want to be) then it's the best way to travel on the cheap and fun.

For slightly longer stays (weeks to months) subletting on Craigslist is an incredibly cost-effective option which comes with locals for roomates as an added bonus.