The google image way isn't too bad. If you're using iTunes, select an entire album of songs, go to edit them (Get Info), and drag & drop the google image result into the "Artwork" box.
It will apply the art to all the songs selected, so you don't have to do one at a time.
Yes, time consuming. Been there.
Also, with iTunes if you create an iTunes Store account (free, don't have to buy anything), you can have iTunes search it's store for any album art, and apply it. Select your entire library, right-click > Get Album Art. Whatever it doesn't find (or whatever it finds incorrectly, which does happen sometimes if you're artist/album naming isn't at least nearly identical to iTunes) you can do manually as described above.
Alternatively, I've used an app called Album Art Downloader in the past: http://sourceforge.net/projects/album-art
It embeds the artwork directly into the mp3's, so they should automatically show up in iTunes and on your iPod. But, it's a bit slow, and it pulls images from Amazon by default, or you can write your own plugin/script to pull images from other methods. I know the Amazon search was pretty ambiguous, and returning some funky results for a lot of my stuff, to the point where I almost had to go through each album one by one anyway to make sure it was the correct art.
That's when I just started doing it through google image search and dragging and dropping.