A maioria das distribuições livres Linux não instalam por padrão o suporte a MP3, por questões legais de patente. O MP3 usa um algoritmo de compactação que é patenteado por seu criador. Assim, a redistribuição de software utilizando um algoritmo patenteado para MP3 é restrita.
A Comunidade de Software Livre de Rondônia tem um artigo que explica isto em detalhes e mostra como adicionar suporte a MP3 em sua distribuição Linux.

O resumo é que existe a biblioteca Gstreamer, que possui plug-ins com suporte a MP3. Este pacote não é livre e por isso exige que você configure um respositório restrito no gerenciador de pacotes da sua distribuição Linux, para que você possa instalar facilmente os pacotes necessários. No Fedora/RedHat configura-se isto para o rpm e yum — repositório Livna — enquanto no Ubuntu/Gnome utiliza-se apt-get e Synaptic — repositórios Universe (não oficial, suportado pela comunidade) e Multiverse (softwares não-livres mantidos pela comunidade).

No Ubuntu

Cito aqui os passos que utilizei para ter o suporte MP3 em um Ubuntu Linux 6.06 LTS (Dapper Dake) e 7.04 (Feisty Fawn) em Português, para instalar o pacote gstreamer0.10-plugins-ugly, devendo-se utilizar uma conta com acesso a administrador (permissão de sudo):

  1. No menu do Gnome, vá em Sistema » Administração » Gerenciador de Pacotes Synaptic. Deve se solicitada a senha para acesso como root.
  2. No Synaptic, escolha o menu Configurações » Repositórios.
  3. Certifique-se que as opções “Software de código-fonte aberto (Binary) mantido pela comunidade (Universe)” e “Software (Binary) Não-livre, restrito por copyright ou problemas legais (Multiverse)” estejam marcadas. Se não estiverem, ative. Depois feche esta janela de diálogo.
  4. Escolha Recarregar (Ctrl+R), para atualizar as informações de pacotes.
  5. Escolha Procurar e pesquise por “ugly”.
  6. Marque para instalação o pacote gstreamer0.10-plugins-ugly e escolha Aplicar.

Pronto. Se você conseguir importar MP3 em seu programa de música no Linux (como o Rhythmbox) mas a saída ficar sem som, talvez este artigo ajude: Habilitando som nas animações em flash no Ubuntu.

Existem soluções ainda mais abrangentes para o Ubuntu, como o script EasyUbuntu, que se propõe a instalar não só o suporte a MP3 no Ubuntu, mas uma grande variedade de pacotes restritos (proprietários) de uso comum, para multimídia, web, compactadores, sistema e voz sobre IP.