If you're a coastal dweller, drive your car (preferably one you can comfortably sleep in) to the ocean. A lot of the beachside hotels are going to have entrances fronting the beach and publicly accessible showers/bathrooms. This may technically be theft/trespassing/etc, but the chances of anyone noticing are nil.
If you want even cheaper than that, buy a good internal frame backpack, a sleeping bag, a tarp, and other supplies, and go hiking/biking/hitchhiking. Couchsurfing can help in this regard.
If you want more traditional, pick a destination. Travel during an off-season and get cheap airfare. Stay in a hostel instead of a resort hotel. Eat the complimentary food if any is offered. Otherwise, stick to primarily raw foods for the duration of the trip with only a few meals out. Stick to primarily free or cheap activities. That should eliminate a lot of the cost of a "mainstream" trip.
Personally, I got my travel bug out of my system (at least for now) backpacking around America over a summer a while back. I rarely travel anywhere and prefer the "staycation"--much more relaxing.