on the mac, many people use Handbrake, but you could also use Quicktime Pro and iMovie for example. Basically the MP4 format for Android devices is similar to the MP4 format that can be played on the iPod/iPhone/Apple TV, so I'd suggest to start with that, and work your way up.
For Windows, check some of the links in my signature.
