You need to embed the album art directly into the MP3 file itself. I don't know how song downloads from iTunes works (they may embed the album art into the MP3, or perhaps store it as a separate file altogether on the iPod), but if you download your music piecemeal, you'll probably find that some songs come with the art embedded but most don't.
I just went through this process myself as I strictly put my music on a 32GB USB flash drive. I used a tool called MP3Tag to go through my song collection and embed the album art into the MP3. I'd download the art from Google Image search using square images that were around 500px to 600px.
Depending on how much music you have it can be a bit of a process but if you're meticulous like me you'll suck it up and get it done