Oh yes, you can fit in 20 gigs worth into it.
When they advertise that it can hold 5000 songs, or up to 5000 songs, they don't tell you the quality of those songs. It's just a nice number to look at.
If you assume (and this is assuming a lot) that the average song is about 3 minutes long, and is roughly 3 megs in size at 128kbps, then you could fit roughly 6,600 songs into that amount of space. If you increase the bitrate to 256kbps, and assume that the files double in size, then you could fit roughly 3,300 songs into 20 gigabytes. (These are very rough numbers.)
When they say 5000 songs, they're probably using a bitrate like 192kbps as a benchmark. So they can half way legitimately say "You can fit 5000 songs (at 192kbps) on this iPod!"
I hope that helps.