There are many different MP3 players on the market ranging in price from 50 bucks up to 500 if you want to spend that much.
I have bought three different kinds.
The first type is an MP3 player that plays MP3s off of a CD. You burn the MP3s straight from the hard drive onto a disc. You can get about 175 songs per disk burned at 128 bitrate (near cd quality). They are the size of a traditional CD player and plays regular cds as well. They can be purchased for 100 dollars and cheaper. Mine had built in skip protection that buffered one minute of song in case you got on some bumpy road.
The second type are ones with built in storage. These can have as little as 32 mb or storage (useless) or up to 20 gb of memory. If you are looking to carry your music with you on the road, these are probably your best options. The apple Ipod is considered the best of this type. You can get the 5gb model for 200 dollars. You don't have to have an apple computer to use these, they are compatible with windows. They also serve as a portable storage device, you can store computer files on them along with your music. Typically, these devices will not skip music on bumpy roads.
A thrid option, which I use, is my Pocket PC. I purchased a dell Axim for under 300 dollars (just bought another one for the gal). The unit comes with memory slots, so you can download songs onto them and carry them with you. You can get memory cards up to 1gb. Since the memory is removable, you can carry as much music with you as you like, switch it out when you want. Battery power is good on the unit. I have read that people have listened to music with the screen turned off for 10 hours and still have power left. The added benefit to using this option is you can get a lot more use out of the pocket pc. You can download maps onto it, use GPS, carry contacts witih you, etc. They attatch to your PC via USB ports. You can also get card readers to put music on the memory faster than through the docking station. These are solid state memory modules (however you can get microdrives for them), if you use solid state memory, they will not skip.
Price is the biggest determination on what you want to buy. If you purchase one, make sure either a) it has a LOT of memory or b)has a way you can swap out memory modules so you can swap out your music.
Transfering music from your own CDs is easy. You can use music match jukebox or microsoft media player to "rip" them from the CDs and put them into a format to use in your MP3 player. It takes me about 2 minutes per music CD to convert the whole CD into MP3s. But you can pick and choose which songs you want to convert over.