En una terminal teclea esto:
sudo apt-get install ubuntu-restricted-extras
y listo.
Nota: No solo se instalan los codecs para mp3 sino una serie de programas utiles pero que no son libres. Si son freeware pero no son free software, bueno eso es por politicas de licencias y todo eso...
Entre los paquetes que se instalan estan por ejemplo el plugin de flash no libre, si usas nvidia instala su correspondiente driver, si usas una inalambrica broadcom te instala su driver, creo que tambien instala la maquina virtual de java de sun, y no recuerdo que otras cosas, pero si lo que quieres es unicamente el de mp3 el paquete se llama gstreamer pero no recuerdo bien que mas...
Buscalo en Synaptic o si no en la terminal
sudo apt-cache search gstreamer
Espero te funcione... Los mismos codecs utiliza vlc, rythmbox, listen y otros programas de audio...
Espero haber ayudado