A while back, I purchased a 30 Gig iPod. I naturally put all my music and some videos on the iPod, but it wasn't until recently that I wanted to add some artwork to view while my songs were playing. I went to the web and got some photos of my artists and began adding the artwork to my playlists.
After checking the necessary options to display album art on the iPod, I found that nothing was displaying. I then found that by unselecting then reselecting the Show Artwork on iPod option, the album art copied correctly then next time I synced it.
[robg adds: This is actually a common method of resolving many album art problems with the iPod; if some albums don't display art, or if some display the incorrect art, doing the above usually fixes it. It will take a few minutes for iTunes to rebuild the album art database, but you should have all your art after that.]
Update: it seems that some people are having problems with this. I've posted a comment below being more precise than the hint, but another thing that helps some people is restoring the iPod from the main iPod screen in iTunes. Album art is stored in a special database on the iPod, not in the actual files, in spite of what you may read elsewhere (it's stored in the files, or in an Album artwork folder on your Mac, but iTunes creates a database when it "Optimizes album artwork").
Mac OS X Hints
http://hints.macworld.com/article.php?story=20060922110329642