I've actually done this (albeit about a decade ago). If you book your tickets more than a week in advance, you can get hefty discounts on Greyhound. These days there are also several other cheap bus companies around the US (Megabus, Boltbus and their ilk) and occasionally the train works out well.
In Vegas, however, consider upgrading to a hotel on the strip. If you can time your visit during the week, hotel room prices halve, and we had an incredible room overlooking the Strip. But otherwise, hostel for sure :)
Another way to save cost - which is what we did - is to travel at night by bus. We didn't sleep very well on the bus, but it saved us some cash.
And the Green Tortoise in San Fran is meant to be one of the best hostels in the world (haven't tried it myself) - I'll definitely be trying it out next time I visit there.