I'm doing a bunch of video encoding for a variety of devices and platforms. I've bounced back and forth a few times between mencoder and ffmpeg. Which do you recommend and why?
Side question: From googling it seems that mencoder uses ffmpeg. Does it do this all the time or only when it deems necessary?
You are right, mencoder uses ffmpeg. Mencoder is actually a universal interface to a number of different codecs or codec libraries like ffmpeg. So, beyond ffmpeg, mencoder can be compiled with support to x264, xvid, lame mp3 and various others that I haven't used. The point is that if you have the correct mplayer/mencoder binary you will get support for many more codecs than the ones ffmpeg supports (especially those with restrictive licenses). Also, you don't lose any of the functionality of ffmpeg using mencoder since you may pass every option you want to the corresponding ffmpeg codec. So I recommend mencoder.
Concerning your side question, you are declaring which codec will be used by mencoder through the ovc and oac command line switches. Try mencoder -ovc help and mencoder -oac help to see which video and audio codecs are supported by your mencoder binary. You may take a look here to find out more about the video / audio codecs. It explains lavc (libavcodec library of ffmpeg), xvid and mp3lame.
Beyond these, I have also used x264 with mencoder which is very useful and I recommend getting a binary with support for that codec.
To append an astray detail after Serafein's excellent answer:
On Ubuntu 11, if you install pre-packaged ffmpeg, it lacks libass, then mencoder can be good in many cases to avoid to install libass by hand, or compile ffmpeg from source. It's good.
