The primary consideration you should have is how you plan to use the thing. There are basically three types of portable MP3 players: Flash based, Hard drive based, CD based. Each lends itself well to different situations.
<b>Classification of player types</b>
CD based MP3 players simply play MP3s that have been burned onto recordable CDs. A CD holds about 650 mb of data. In terms of physical functionality they are more or less identical to a regular discman, which means they are not suited to vigorous physical activity, like jogging - they will skip.
Flash based MP3 players store MP3 files in flash memory. Flash memory is simply physical memory kind of like RAM that can store files and be written over. Flash memory can be physically very small, so the smallest MP3 players will use flash memory. Flash memory also doesn't require any moving parts, which makes it good for physical usage - jogging for example. Flash based MP3 players typically have 64, 128 or 256 mb of memory.
The last kind is hard drive based. These MP3 players store data on a small hard drive, often similar to a hardrive on a laptop computer. These typically are large - sometimes as large as a discman - although they are getting smaller all the time. These have large storage space - anywhere from 5 to 60 gb (1 gb = 1024 mb). The hard drive does have moving parts and they tend to be a bit large so they are not great for jogging.
<b>How to interpret storage space</b>
A music CD stores audio information in (modified) WAV format. When you copy music tracks from a CD to a computer, you get these WAV files. WAV files have high audio quality but they are large - a CD, which is about 650 mb stores - 74 minutes of audio.
The MP3 format was designed to make files of high audio quality (though not as high as a CD) at much smaller file sizes. This is accomplished through lossy compression. MP3 encoders take a WAV file (from a CD perhaps) and encode it into the MP3 format. Most (but not all) of the audio quality remains but the size is typically an order of magnitude smaller.
For any MP3 encoder, there is a simple trade-off between file size and quality of audio. MP3s can be made at varying quality bitrates, ranging approx. from 32 KBPS to 320 KBPS. KBPS = Kilobits per second. The higher the bitrate, the more closely the MP3 will sound to the original WAV file, but the larger the resulting MP3 file.
The sweet spot for music MP3 encoding will fall between 128 and 192 KBPS. At this bitrate only trained listeners with high quality audio equipment can distinguish between an original and a MP3 file. Lower than this tends to sound pretty poor; extremely diminishing returns hurts bitrates above this.
To give you a sense of how bitrate translates into storage space, lets take an example: A four minute song (typical for pop music) encoded at a constant bitrate of 128 KBPS (pretty typical)
(128 kilobits/sec) * (240 seconds) * (1 kilobyte /8 kilobits) * (1 megabyte / 1024 kilobytes) = 3.75 megabytes.
So, an MP3 player with a total capacity of 64 megabytes could hold about 17 songs that were 4 minutes each recorded at 128 KBPS. An MP3 player with 128 mb could hold twice this much.
The final question is how you came by your MP3 files. If you downloaded them (and that is typically illegal for copyrighted music, shame on you) then somebody else encoded them. Just open up windows explorer and highlight the MP3 to see how large it is.
If you encode your own, you can pick a bitrate in the encoder, and thus control file size and quality.
<b>1.4 Ghz AMD T-Bird underclocked to 1 Ghz...just to be safe!</b>