Se a sua distribuição tiver um gerenciador de pacotes (a maioria faz hoje em dia), simplesmente use isso. Pode fazer parte do pacote 'mplayer' ou tem o seu próprio pacote
No Debian isso seria (veja os comentários):
sudo apt-get install mencoder
Se você não for root ou não tiver um gerenciador de pacotes, baixe a fonte do link e instale como um programa normal, provavelmente algo como:
./configure
make