Hello everyone, looks like I have "moved away" from building my MAME cab to something a "little" more practical, a jukebox

Reason behind this is because I have a GREAT set of DCM 10" floor speakers and a 600w Kenwood amp in the garage, and instead of letting them sit there and rot, I have decided to try to find something to do with them.
Ok, to get the easy stuff out of the way first. I have a small MP3 collection that I have built over the last 10 years or so. Of course all of them have had the ID2/ID3 tags stripped. So basically all I have are MP3's with nothing more than a filename used as a title/artist.
I would like to get all my MP3's in "good" shape, if that makes any sense. I got an iPod a few months back, and couldn't beleive how cool it was to download MP3's from iTunes and get the artist, title, cover art, genre, etc to display on the iPod. Now whenever I listen to my old non iTunes MP3s on my iPod and get nothing but a filename, I get depressed

I want my MP3's to all be built like they had all been downloaded from iTunes, for consistency within my iPod and new jukebox. So starting with nothing but a filename, what would be the best way to go about getting my MP3's in order.
I've seen some apps. that will take a filename and break it down into ID3 tags. But when it comes to album art, genre's, etc does it come down to a manual process hanging out all night on wal-mart and amazon.com, or is there type of program that I can run the MP3's through to grab certain kinds of info? Thanks!

EDIT ------ (Forgot to add this) -------------------------------
Currently my MP3's are all in one folder. I've seen some links on here for album cover art search apps, but from what I can see there has to be a certain file structure before this will work...
Also wondered where the album cover art is stored as it not actually written in the MP3 tags... So really its two seperate files joined by some type of link or pointer?