FFMpeg

FFMpeg is an extremely powerful tool for converting video from one format into another format.  All major codecs are supported, and even a lot of more obscure ones.  Unfortunately, the only way to use this tool directly is by typing in commands on the command line. 

To enter commands, you need to start a "Terminal" program.  In Ubuntu you can get to it by going to Applications -> Accessories -> Terminal.

Once there, you can type commands to run programs.  (Two important, but non ffmpeg-related commands: ls - lists out all the files in the directory you are currently in, and "cd" - changes the directory for example type "cd Downloads" from your home directory to get into the Downloads directory.  Your prompt will show your the current directory, the tilde "~" means your home directory /home/username/)

The first two things you can do with FFmpeg are to list out the formats and codecs that this copy supports.  This may change based on what is installed on your computer, so it is best to check these before running a command, to make sure you have the correct support available.
To list all container formats type: ffmpeg -formats
To list all codecs type: ffmpeg -codecs

To convert a video, simply run the command "ffmpeg" with four additional parts:
ffmpeg [input] [video options] [audio options] [output]

The input part is composed of a "-i" and the name of the video you have that you want to convert to something else.  You could have more than one of these input files (each one gets its own "-i") if for example you have a video with an audio track in a seperate file.
ffmpeg -i InputVideo.mpg ...[video options] [audio options] [output]
ffmpeg -i InputVideoTrack.mpg -i InputAudioTrack.wav ...[video options] [audio options] [output]

The video options are where you specify the codec (with the "-vcodec" option) and bit-rate (with the "-b" option). In addition you can specify a video preset ("-preset") which x264 encoding won't run without (some easy presets: slow, medium, fast), and you can specify a size ("-s") with either a standard size reference or the format WIDTHxHEIGHT.
ffmpeg [input] -vcodec mpeg2 -b 3000k ...[audio options] [output]
ffmpeg [input] -vcodec libtheora -b 3000k ...[audio options] [output]
ffmpeg [input] -vcodec libx264 -preset medium -b 3000k ...[audio options] [output]
ffmpeg [input] -vcodec mpeg2 -b 3000k -s hd480 ...[audio options] [output]
ffmpeg [input] -vcodec mpeg2 -b 3000k -s vga ...[audio options] [output]
ffmpeg [input] -vcodec mpeg2 -b 3000k -s 1280x720 ...[audio options] [output]
The audio options are where you specify the audio codec ("-acodec") and bit-rate ("-ab").  It is also possible to specify no audio ("-an") to get only video in the output file.
ffmpeg [input] [video options] -acodec flac ...[output]
ffmpeg [input] [video options] -acodec libmp3lame -ab 256k ...[output]
ffmpeg [input] [video options] -acodec libvorbis -ab 192k ...[output]
ffmpeg [input] [video options] -acodec libfaac -ab 192k ...[output]
ffmpeg [input] [video options] -an ...[output]

The output is where you specify the filename that the converted video will go into.  Usually the extension of the filename (.mkv, .mp4, .avi, etc) will allow the program to determine what format the file will be written as, however if it is ambiguous or you want to use format that isn't tied to that file extension, you can use "-f" and the format name.  (These commands will all output the video file in the same directory you are currently in.)
ffmpeg [input] [video options] [audio options] OutputVideo.mkv
ffmpeg [input] [video options] [audio options] OutputVideo.mp4
ffmpeg [input] [video options] [audio options] -f dvd OutputVideo.mpg
ffmpeg [input] [video options] [audio options] -f matroska OutputVideo.vid
ffmpeg [input] [video options] [audio options] -f mp4 OutputVideo.vid
ffmpeg [input] [video options] [audio options] -f avi OutputVideo.vid

The result could look like:
ffmpeg -i InputVideo.mpg -vcodec mpeg2 -b 3000k -s hd480 -acodec flac OutputVideo.mkv

Two Pass Encoding
It is possible to use ffmpeg for two-pass encoding.  The important part is to call it twice, once with the "-pass 1" parameter and once it finishes run it a second time with the "-pass 2" parameter.  On Ubuntu, you can do a couple additional things on the first pass to speed it up: "-an" specifies that there is no audio codec to be run.  "-f rawvideo" keeps it from trying to pack it into a special format, just to throw away.  The "-y /dev/null" specifies that the output will go into the special null file, which means that it just disappears instead of having to send data to the hard disk.  In addition when running two pass, we add the "-bt" parameter which tells the codec how much the bit-rate can change.  It will usually work well to set it the same as the bit-rate.
ffmpeg -i InputVideo.mpg -pass 1 -vcodec mpeg2 -b 3000k -bt 3000k -an -f rawvideo -y /dev/null
ffmpeg -i InputVideo.mpg -pass 2 -vcodec mpeg2 -b 3000k -bt 3000k -acodec flac OutputVideo.mkv

That's all there is to using FFMpeg, not too complicated.

Now lets do an example using FFMpeg....
ffmpeg -i sintel_clip_ffmpeg.mkv -pass 1 -vcodec libx264 -preset slow_firstpass -b 1200k -bt 1200k -an -f rawvideo -y /dev/null
ffmpeg -i sintel_clip_ffmpeg.mkv -pass 2 -vcodec libx264 -preset slow -b 1200k -bt 1200k -acodec libfaac -ab 192k output.mp4

As a bonus, we can set it up so that it can be run from a website, and the video will start to play before the download has finished:
qt-faststart output.mp4 webvid.mp4