I've tried several different players and gone back and forth with formats (wmp or mp3) and here's what I'm using now:
Axim X5, with Windows Mobile 2003 (never patched or updated since Sep 2003.)
Player is
GS Player which looks like it had a recent update to 2.0. I'm still using 1.96.
Format I use is mp3 at a 96 rate. 64 just didn't sound good enough in my car. 96 was the compromise between sound quality and storage quantity.
I use just the basic Sony walkman type headphones or a cassette adapter in my car. The cassette adapter was the standard Target/WalMart variety for less than $20. For longer trips I'll also plug the Axim into the car charger cable to keep it fully powered up.
Songs are stored on a 1gb CF card. I did have problems using wma files on the CF card, but mp3 has been fine (on the same card!)
This set up has worked for me.