From Amarok Wiki
Automatic Installation
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...
Manual installation
Should the easy-installation fail, you can still install the needed packages seperately 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 gstreamer0.10-plugins-ugly
kubuntu-restricted-extras package
If you want support for most other formats as well you might want to consider installing 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.