To reclaim that space, simply go into the iPod preferences in iTunes and uncheck the 'Display Album Art' option. When I did this on my 60GB iPod 5G that had about 20MB free, I was able to reclaim over 1.5GB (yes, that's GB).
I have tested and verified this with a 60GB iPod 5G and a 4GB iPod nano that were formatted for a Mac. However, this should work with all iPods that can display album art and regardless of Mac or PC format.
[robg adds: From an older hint and its associated comments, you might also see some space savings by unchecking the Artwork tag in the Get Info box -- apparently the MP3 tags also contain information on the artwork, even though the iPod is using a database to track it. Given the age of the hint, I'm not sure if it's still relevant or not; please comment if you have more info on the subject.]

