You have to append the artwork to the actual music files themselves. What I do is search Amazon.com for the album that the songs are off of, click the artwork so it expands and then right click the larger artwork and COPY.
Then in iTunes go into "get info" on the song, and paste the artwork in the artwork tab. This will append it to the file. Yeah yeah i know it isn't technically legal to "copy" the artwork but I honestly don't give a rat's *** about doing it and neither should you.
(...cue finger-waving "shame on you, you're breaking the law" post...)
Then once you transfer this song you put the artwork on to your nano, it should show up there when you play the song. At least this works for me on my 30GB iPod video.