I am obsessive about my music collection - you can say that I actually suffer from obsessive compulsive disorder when it comes to digital music - I like everything to be properly tagged, with cover arts. I remember, last year, when I bought my iPod, I spent an entire week sorting my entire collection. Initially I was manually updating some 4000+ songs, but then, I came across some good tools. So this post is mainly about those tools.
First is the TagRunner - this software automatically searches for missing tags in your music files. So the major part of your tagging problems are taken care by it. Next, if you use iTunes to listen to music, Tunesleeve can be used to search for album arts for each of the albums. It looks into your iTunes library and updates the cover arts of most of the albums (assuming all your songs are properly tagged with the correct albums).