You filled your iPod with all your favorite music, all legal of course, no p2p downloads. If you bought your music from iPod's music store then you would get nice album art to go with your collection, but not all of us are that fortunate, so you settle for just seeing the song and artist's name.
Well, I proudly present to you, Artie, the best iPod utility I have ever used. Artie lets you select a group of songs from your iTunes and searches for the album art and automatically updates your music collection. You can find Artie here.
Artie is still a work in progress, don't worry it won't damage your iTunes music collection, it will only abort but you can always restart it. Another bug I found was that it cannot handle real long lists, so 50 songs at a time would be appropriate.