1. Descargar los codecs:

http://www.mplayerhq.hu/design7/dload.html#binary_codecs

En mi caso pinché sobre el enlace 'http' justo a la derecha de 'Linux x86 20071007'

2. Descomprimir los códecs. En mi caso:

tar xvfj essential-20071007.tar.bz2

3. (Como root) copiar los códecs a su sitio. En mi caso:

cp -Rv /ruta/essential-20071007/* /usr/lib/codecs/