From Amarok Wiki
(Redirected from MP3:Debian)
Installing MP3 support on Debian Lenny (stable)
Xine
You will need to install "libxine1-ffmpeg"
sudo apt-get install libxine1-ffmpeg
GStreamer
sudo apt-get install gstreamer0.10-plugins-ugly
This should be applicable to Debian testing and unstable as well.