I've tried something similar. First, you will NOT have enough memory on the uC to store a real song. You'll need external memory to handle that. That means using an SPI interface to external flash or EEPROM or something. SD is also good - I believe it's an SPI style interface. There is code out there for the ATMegas to interface SD.
Second big deal is to get the data in a proper format. The way I would do this is to use PWM to create the varying voltage levels. I believe you have a 16-bit PWM on that uC so you can have 16-bit fidelity on your sound. If you have problems with space you can use 8-bit PWM instead. So your sound data has to be in 8 or 16 bit PCM with 0x0000 being lowest value and 0xFFFF being the highest. If you want high-fidelity music you'll have to have a sampling rate of 44KHz to get all of the good harmonics and such. I believe this is PCM - same as it is called on the PC.
So then you'll have all of these values - for five minutes of music you'll have 5 * 60 * 44000 = 13200000 16 bit values which is 211200000 bits (211 megabits, 26.4 megabytes). Those are your storage requirements for raw data. MP3 is a possibility - there are external chips for that, but you'll still have large space requirements.
So every 1/44000th of a second you'll update a value in a PWM register. Your PWM frequency will have to be higher by 4 or 5 - ie, 5 PWM cycles per value.
That's your general algorithm - update values in a PWM register and let it go until the end. You will need at least a filter on the output - limit frequencies to the audible range of 20KHz (more if you're an audiophile). An RC filter will work but I would go for an active filter BECAUSE if you're using PWM your output range will be from 0 to 5V usually with the average voltage being about 2.5V. Speakers don't like DC levels - just signals. Pretty sine waves that have a 0 mean voltage. So your active filter will have to adjust the voltage levels and use dual supplies to provide negative voltages. You can also amplify the signal for the big pumping bass. Just don't blow out your speakers.
MP3 is probably a better alternative to PCM. There are chips out there: http://www.sparkfun.com/commerce/product_info.php?products_id=8892
That is however a whole microcontroller. And you already have one. But let's face it - the ATMega isn't going to do MP3 on its own soon no matter how you jazz it up.
It looks like the waveshield referenced above basically does this - uses SD for the storage of PCM and an external amplifier for the sound. Good Luck!