My main iPod is a 40 (I have about 25GB of music/audiobooks right now).
I've found my Mini (and my g/f's) holds a little less than 900 songs. Basically, I've just been using it at the gym and on the commute to work. I've pretty much gone through and put in a few hundred songs that I must have.
Then I filled the rest with stuff that interests me right now. I figure when I've gone through a good portion of it, I'll simply swop it out with a few hundred new songs.