I got most of the formats working except H.264
Used this command to get most of them working

sudo apt-get install libavcodec-unstripped-52 libavdevice-unstripped-52 libavformat-unstripped-52 libavutil-unstripped-49 libpostproc-unstripped-51 libswscale-unstripped-0

Am running mint 9 on a dell inspiron E1505
Also I want to render 4 minutes of 720p HD video at 30 FPS. What codex shoud I use for the most compression without quality loss.

If the H.264 options are disabled, then it is probably because you are missing an AAC encoder. Ubuntu 10.04 uses unstripped ffmpeg libs based on a 0.5 version of ffmpeg from Debian. Mint9 is probably the same. This version does not contain an AAC encoder, but anything newer based on ffmpeg v0.6 does.

Well for some reason you have to restart your computer after installing the unstriped codexes. Works fine now. :DUH: