I understand the problem with carrying around a CD book, didn't know if that was going to be an issue for you though.
NoKarma brings up a very good point though; I've messed around with a MP3 system (never got it into the car, since I decided I should spend time working on semester projects, and such) but ran into the same problem; how do you find one song out of that many? My solution was to step back and think how many controls do I really need, then implement only those.
I ended up only using "next", "previous", "shuffle" (toggled it on and off, just an interface to winamp), "play", "stop", and "pause"
I left winamp's "repeat" on, and figured I'm more likely to just keep hitting "next" until I find a song I feel like listening to rather than deal with being able to play a particular song (that and I couldn't figure out a good way to put a keyboard in my car)
FOTBR