The first thing to do would be to break up gameplay into a number of different "states" that would correspond to different music tracks. For instance, if the player is getting shot at, then fight music should probably be playing.
I'm pretty sure I've made mention of Total Annihilation elsewhere in the forums, so allow me to make another reference to it:
TA has the ability to play music CDs. MP3 wasn't popular when the game came out, so music CDs were as close as you could come. However, it had the ability to control it via several means:
1. You could do random tracks off the CD
2. You could just do a straight play-through
Naturally, those two are standard on any CD player out there. However, it also had #3:
3. The ability to assign tracks to certain events, and play them when those events occurred. For instance, if you were just sitting around building, it would pay tracks that had been selected for "Building." If you were fighting another player (shooting his units and such), then it would play tracks from "Combat." If you were losing, or had lost a bunch of units and whatnot, you could select "Defeat." There were a few others, but those are the ones I remember (and I'm in Linux, so I can't check it right now).
I think we could have something along this line - get the best of both worlds. If the player wants to simply play tracks from the playlist, then they can. However, we can also assign meaning to particular songs, having them play when certain things were happening in the game.
So in short: What whitelynx said. ;-)
~Brian