iTunes makes it really easy to download album art for an entire music library in one fell swoop (select-all, Advanced->Get Album Artwork). It's a little trickier to embed the artwork into the MP3s themselves (for use with other players like WinAmp). I found a perl script at Teridon's iTunes Scripts called itunes_insert_artwork that does a nice job.
While trying it out, I noticed that a lot of the jpegs from iTunes were ridiculously large. Some were over 800K, for a 600x600 image. Not quite sure why - resaving them even at 100% quality resulted in much smaller files. So, I tweaked the script to send the images through ImageMagick first. (At quality 85, those 800K images get down to 200K.)
You'll need to have ImageMagick and PerlMagick installed. If you plan on installing ImageMagick/PerlMagick for ActivePerl, note that, currently, you'll need the older 5.8.x version to get it to work.Download the script