This shouldn’t be all that difficult if you have an aptitide for building circuits and programming, because of the variety of interface adaptors, UARTs, etc. available. You’re probably looking at just a few ICs and some linear components to get a usable player. You’ll need a CPU (doesn’t have to be a hot-rod because you’re not doing 10,000 things at once like a PC), some RAM, some flash ROM for your program that runs it (your firmware), one or more interface adaptors depending on what your storage medium is, a display of some sort, and DACs and linear circuitry for the audio-out, and an enclosure with buttons, etc. As for MP3s, you can get MP3-reader ICs: you just feed it a string of MP3 frames that you read from your storage; it outputs PCM you send to your DAC. Because you’re programming it, you can put all the flexibility you want into playlists, functionality, navigation and all that.
I want to start moving away a bit from MP3 and toward formats like Vorbis, so I’d do mine in software; that’d allow for FLAC, WAV and others too. The increasing capacity and decreasing expense of memory cards makes them practical now. I’d build maybe eight slots, and use MMC (open standard) or SD (partially-open). And my specialty--linear audio--I’d just the way I like. :) It’d take ordinary AA batteries: at least four of them, for higher-power audio out.
This is all a ways off though; I haven’t even researched CPUs and adaptors that nuch. It’s not a huge priority.
