I agree about mencoder being able to do almost anything. I learned to use it from using
mplayer, and I think that's the best way to approach it. The options are reasonably straight
forward (most of the time).
I find mencoder to be more capable than transcode / gstreamer / vlc, but none of them can do
everything, and most of them I don't know them quite well enough...