A car obviously gives you much more flexibility. And though local public transport in Brazil is pretty decent if not awesome, it is not very usable for users who don't speak Portuguese. In fact, in my experience, the most common way for Brazilians to find their way around using local public transport in a city they are not familiar with is to ask around. Good luck with that if you don't speak the language.
On the other hand, big Brazilian cities tend to suffer from very busy roads, which might not be to your enjoyment.
A good place to search for bus routes is Plataforma10. This site's interface is available in English. However, also in my experience, for somewhat less common routes, Plataforma10 doesn't always return results.
Rome2Rio, as was pointed out by @joernan, is also a good place to look for connections. But... I've found that, at least for South American connections, they don't always carry the latest information. (For example, they claim that Util travels between Rio and Petropolis, but Util's website does not support that claim.)
However, also through Rome2Rio, Guiche does travel between the two and buying tickets online might be possible. Their site is in Portuguese, but a booking process is pretty much the same in every language. Keep in mind, though, that some Brazilian bus companies only sell tickets online to users who have a CPF, which is somewhat similar to a Brazilian Social Security Number. You can always buy a ticket in person without a CPF. And, the bus station from which your desired connection leaves will always (well, almost always) have an office of the company you want to travel with.
Then, there's BuscaOnibus, which also has an interface in English. At least in this case (Rio to Petropolis is what I checked), they seem to be exhaustive.
