Going by bus, Rio de Janeiro
I enjoyed my trips by bus to Rio and Brasilia a lot, as the coaches were very luxurious. Okay, the trip itself cost me two times 14-17 hours, but when you arrive, you just forget about everything!
Drivers change every so often as to not to get too tired, and, as everywhere, some are better drivers than others!
In Rio, you get your tickets to other Brazilian destinations at the Rodovaria. Just look at the signs on top of the counters, stand in line, hold out your passport, buy your ticket (preferably visa or cash, I guess) and keep the copy of it to show your driver. He will put a tag on your bags so they don't get mixed up.
My trip to Brasilia was some 140 R$, which is not that expensive. Especially if you see that we traveled first class. If you can: please DO take first class, you won't regret it: the chairs are much more comfortable, you can close up every curtain around you, you get free coffee and water, ...
The coaches are completely equipped for sleeping, but be sure to take a pill to relax a little.