In my quest to stop using xmms (it requires that whole.. mouse thing) I ran across a mp3 jukebox server called mserv [mserv.org].
It's pretty cool and can support just about anything I want it to since it uses external programs to play them. It uses a server protocol similar to that of Joe's Moonshot Jukebox. I don't have any oggs so his jukebox is mostly useless to me.
I quickly hacked together a script (well, it functions as several tools) to let me play songs more easily. It's called mq and you can see it here if you want. With it you can do things like: mpick Cake | mq to enqueue all tracks matching "Cake"
Put it in ~/bin/ and have it propogate its tools with symlinks by doing mq -setup. Look at the code to figure out what does what, it's fairly straight forward.