Mplayer je v repozitáři multiverse. Stačí jej povolit (např. ruční editací /etc/apt/source.list, na konec řádku kde máte repozitář universe připište ještě multiverse). Pak už jen klasické:
sudo apt-get update && sudo apt-get install mplayer-***
kde *** je typ vašeho procesoru (386, 686, amd6, k6 atd.).