Depends what you want to do. Lots of people put their whole catalog on them at a very high quality, so 60 gig is nice. I can get by with 2 gig myself. I can put 100 or so songs on at CD quality bitrate which works great. I am constantly swapping out songs on it so the lower memeory works fine. I usually only listen to 5-10 different artists at any one time and then when I'm tired of them move on to somebody else.
Sorry, I meant how much memory do you actually use?
My music collection exists on CD and DVD, but if I hadn't bought the disks, I guess it's conceivable I'd want to store it all on an iPod or other device.
I love music and all types of music. I think that I would need atleast 1 Gb of space. I would use the 512 MB though, I would just replace the music every few days or so.