I no longer use a dedicated mp3 player in the car. I use my phone (Droid Razr which has a 32G microSD card) with a windshield mount that has a charger that plugs into 12V accessory jack. Not only can I listen to mp3s stored on the card but I can also stream music from sites like Pandora. The phone also provides GPS and even makes/receives phone calls!
As far as a dedicated mp3 player, generally speaking, the lower the cost, the less on-board storage it has. As already mentioned, Sansa has some inexpensive models starting around $40 for a model called the Clip Zip. At that price point you get 4G of on-board storage and a microSD card slot for expansion