The GSSMP developers recommend storing your music in Ogg Vorbis format, rather than MP3. For a good explanation of why, check out this article: http://www.linuxjournal.com/article/4416, especially the section entitled "What's Wrong with MP3?".
Anyway, if you do want to be able to play back mp3 files, and you're happy to install something that is not Free Software (details from Fluendo) you can install the Fluendo mp3 gstreamer plugin. On Ubuntu enable the universe repository and type:
sudo apt-get install gstreamer0.10-fluendo-mp3
Other distros should check their package repository, or read more at http://www.fluendo.com/resources/fluendo_mp3.php