DO NOT use Windows Media Player for album art unless you are using wav files (in which case you don't really have a choice). WMP will cause tons of headaches with mp3 album art if you ever use the mp3's outside of WMP.
Like weasle said, use tag&rename. It automatically grabs the art from Amazon.
Media Monkey is definitely the best way I have found to get Album Art, and even better, it'll apply the art to entire albums at a time.
However if there is something more obscure that Media Monkey can't find, manually search Amazon for it. If not there, try Google images. And last, try going to the artist's actual website and visiting the discography section, as they usually have album art.
I have 35Gb+ of music and I have album art for all but maybe 10 albums. For the few that dont have album art, I made a simple Photoshop template where I can add in text info about the album and artist that still looks visually pleasing to the eye.
I like Tag & Rename's interface a little bit better, BUT, Media Monkey is free, which you can't beat. There is a Media Monkey Gold that you can pay for, but album art tagging is included in the free version. And yes, both T&R and MM will add album art to the album folder AND embed it to the files.