There are several chipsets on the market for digital music decoding that can be controlled by an Arduino, but using them requires the ancillary hardware such as a memory card reader, analogue output sockets circuitry and so on. After a few moments planning it can often seem that the total cost and effort will reach the cost of a consumer portable MP3 player.
So why not instead get a cheap portable MP3 player, remove the circuit board and mount this on a shield? Then you can simply wire the buttons to be controlled by your Arduino and it's done. This is exactly what Instructables user "dresch" has done - with great success. They now have an Arduino MP3 shield for less than $40 (or even less if you use a protoshield).