Você precisará instalar estes:
sudo apt-get install ffmpeg libavcodec-unstripped-52 libavdevice-unstripped-52 libavformat-unstripped-52 libavutil-unstripped-50 libpostproc-unstripped-51 libswsclale-unstripped-0 x264
Em Karmic, Lucid e Maverick, você deve substituir "unstripped" por "extra", mas como existem pacotes transitórios, este trabalho também.
E então você pode usar um script com:
for i in *.avi; do ffmpeg -i "$i" -f mp4 "'basename "$i" .avi'.mp4";done
E você pode usar opções como essas para configurar a resolução, codec de vídeo, codec de áudio e qualidade de áudio:
for i in *.avi; do ffmpeg -i "$i" -s 352x288 -vcodec libx264 -vpre default -acodec libmp3lame -ab 192k -ac 2 -ar 44100 -f mp4 "'basename "$i" .avi'.mp4";done