I have interfaced the Arduino to the VS1053 decoder solution from VLSI to create my DIY mp3 player...
It can actually play lossless FLAC at even 1000kbps, but that's pushing the 16mhz Arduino to its limit!
It uses the awesome SdFat library to read from the SD card.....
I have tried to extensively document the creation of it at my blog at
http://kalum.posterous.com/50759184
I hope the information will be useful to anyone who is interested in mp3 decoding/SD card reading etc....