MP3Tag is very easy to use. Just download and install it.
When you start MP3Tag, you can choose to open folders or individual files. Pick a folder containing the album you want to tag with album art. Select the songs and then right click and choose "tag properties" (I think it is). There you can edit all the tags and add album art.
It is best that you prepare the album art in a separate software. I usually download album art and then change the size to around 340x340. This works on all my MP3 players.
I do not know how the Sony A series work. Perhaps they need a file called "cover.jpg" or "folder.jpg"? Rockbox DAP's used to require a "cover.jpg" in the album folder for album art to work. However, from version 3.9 Rockbox can read embedded album art.
You can look here for some tips:
http://www.avforums.com/forums/portable-music-mp3/1324637-sony-nwz-a845-does-not-display-album-art.html
http://www.sony-europe.com/discussions/message/638570
http://ubuntuforums.org/showthread.php?t=1612302
As you can see in these threads, there might be a problem with the ID3-tags. They need to be V2, preferrably 2.3.
The best thing is if you try different suggestions and see which one works the best.