I'm sure you're after a GUI method(if you're not, then check for mencoder and ffmpeg), if so I'd highly suggest VLC.
It's a cross-platform media player that supports every format you can think of, without any codecs needed for installation(it can also play damaged or partially downloaded files!)
Plus, it doubles as a media converter. When you install it on whatever distro you're using(You're using Ubuntu, right? If so, install vlc from synaptic), run it, click on File, then Wizard. Choose Transcode, and then follow instructions from here

Hope this helped,
Extreme Coder