On most Linux systems you will not have an MP3 codec. This is because of the copyrights of the codec. But you can install it by hand.
For Ubuntu use this page: http://po-ru.com/diary/fixing-ffmpeg-on-ubuntu/
I had to change the lines from:
confflags += --enable-mp3lame --enable-faad
confflags += --enable-faac --enable-xvid
to:
confflags += --enable-libmp3lame --enable-libfaad
confflags += --enable-libfaac --enable-xvid