How to correctly choose a memory?
Basing on the discussion let me compile the answer -


EEPROM/flash solution seems to be the easiest one, and MSP430 is having built-in interface for them, but there're several drawbacks: you will need to implement manual error handling/correction; chip is not removable; and finally it may wear (you may need to implement wear leveling stuff).
I recommend to focus on the slightly different architecture:


use SD-card as a storage through SPI; it will perform all low level tasks for you, is removable, and intended for frequent rewrites, and in general more convenient;
however you will need to implement file system handling of the volume, I came across Elm-Chan's Generic FAT file system module with sample code to control MMC/SDSC/SDHC (FatFs), I did not use it myself but heard positive feedback about it; it seems to support your MCU;
you may consider using special IC for MP3 decoding - it will free computing power of the MCU for something more useful than doing MP3 decoding. I know about VLSI Oy from Finland, I am sure you will find more manufacturers (through e.g. Digikey). Note that these chips are having MP3 and other codec licence with them, thus you will be legally clean in this respect, if at some point of time you will decide that you device it good to be sold on the market.



Edit: @AndrewMorton pointed to MP3 press release stating "licensing program for certain mp3 related patents ... has been terminated", if you follow the further link you can see


  However, the end of the mp3 licensing program does not automatically mean that all mp3 technology is available license-free now. Apart from the core mp3 patents included in the licensing program, there might still be some implementation–specific patents (or patents for other functional enhancements) that have not expired. Thus, manufacturers will have to check the situation regarding their intended products first before including mp3.


Thus there might still be a legal risk.