apt-getでも入ったと思いますが、ソースからインストールする方法を紹介します。
ubuntuは14.04 64bit の場合になります。
h264のエンコーダにx264を使う場合を想定します。
sudo apt-get update
sudo apt-get install build-essential automake autoconf zlib1g-dev libtool libx264-dev yasm
wget http://ffmpeg.org/releases/ffmpeg-2.6.tar.bz2
tar xjf ffmpeg-2.6.tar.bz2
cd ffmpeg-2.6
./configure --enable-libx264 --enable-gpl
make
sudo make install