I did this recently myself like this;
(I'm making the assumption cover art is called "Artist - Album.jpg")
1) Import all cover art into MC
2) Select all cover art in MC, right-click and select Library Tools->Fill Properties From Filename
3) Type [Artist] - [Album] into the Filename text box, make sure Directories is checked off, Click OK
4) Make sure all cover art is selected again, right-click and select Library Tools->Rename File From Properties
5) Directories should be checked on, your music Base Path set to the correct path (e.g. D:\Music), rule would be [Artist]\[Album], Filename checked on, Rule should just be "Folder" (without the quotes obviously), click OK.
6) Make sure all cover art is selected again, right-click and select Delete
7) Check "Remove from Media Library" and click OK
Go to Tools->File Location, Location Rule should be "Next to file (Folder.jpg)".
9) Select all your albums, right-click, go to Cover Art->Remove Cover Art, select NO when it asks if you want to delete for files.
10) Select all your albums, right-click, go to Cover Art->Quick Find in File / Cover Art Directory
I'd try this on a few files first before going for the "big push". Also, this won't work for (Multiple Artist) albums, but it can be adapted to; in point (5) replace the Base Path with, for example, D:\Music\Assorted, and the rule to just [Album].
Hope this helps some, your directory structure and cover art filenames need to be pretty well organised for it to work well.
And please don't sue me if it buggers something up, this is all at your own risk!
All I can say is it worked great for me.