a quick ebay search for "shuffle A1204" returned a few auctions for 2nd generation 1 gig ipod shuffles.
The shuffles don't have a harddrive, they use built-in Flash memory.
How many songs you can shove into your shuffle depends upon the size/quality of the songs. The higher the quality, the bigger the file size and the fewer that'll fit in your player.
Shure e4s are pretty nice phones. They are miles beyond the quality of sound that comes out of the "stock earbuds" or anything that you can pick up at walmart for $20. I mention this simply because they will exaggerate the poor quality of lower bitrate music.
The Shure phones are also isolating in design. the better the quality of seal or fit, the better the quality of sound they will produce for you. When inserted properly, they should "muffle" outside noises, like wearing ear plugs.
Mp3 are "compressed" versions of the songs. The lower the bitrate, the smaller the file, but the worse the quality. People will throw around numbers like 256, 128, 192...320. Some people will even drop "lossless" in your lap.
Anything below 128 is comparable to FM quality and will sound like crap with your player.
192 is a great compromise of file size and quality for non critical listening.
256 and 320 is near CD quality (its really hard to discern the difference between the two in loud environments where you will probably be using your portable rig).
Lossess are CD quality and the largest of file sizes. These aren't a compressed format like mp3, they are flac or aac. I think media monkey calls their format ape.
Now, how do you get your favorite CDs onto that little shuffle?
You'll need a ripper and the software for sync'ing. Itunes does both, Media monkey does both. They have excellent "help" sections and just google'ing your question will provide you tons of guides or how-to's. "how to rip a CD in itunes" will yield about a gazillion results.
Welcome to the world of portable audio. Its not a complicated as it sounds.
*Insert joke about your soon to be empty wallet here*