From Amarok Wiki
Since versions following Kubuntu 6.10 (Gutsy Gibbon) the Amarok package ships with a special feature which allows you to easily install MP3 support on any Kubuntu version released after the year 2006. This usually works perfectly...
libxine1-ffmpeg package
Should the easy-installation fail, you can install the package libxine1-ffmpeg using your preferred package management application (e.g. Adept or KPackageKit). Or to install it manually, enter the following command in a terminal such as Konsole:
sudo apt-get install libxine1-ffmpeg
kubuntu-restricted-extras package
libxine-ffmpeg only installs playback support, therefore you might want to install kubuntu-restricted-extras using your preferred package management application. To install it manually, enter the following command in a terminal:
sudo apt-get install kubuntu-restricted-extras
In Kubuntu releases prior to 9.04, before installing this package you first need to enable the Multiverse repositories in /etc/apt/sources.list . kubuntu-restricted-extras will install MP3 support for the MusicBrainz tagging feature and install the k3b MP3 plugin. It will probably make sense to install this package if you are using Ubuntu or Xubuntu, since it only depends on KDE applications which are used by Amarok anyway.