I am having trouble figuring out how to add album and artist images on my phone. I have a Galaxy S4 and I use the default Samsung 'Music' app. Other than this issue it works nicely.
I had the same issue with my Note 3.
If you have the entire albums, or maybe without, Album Art Grabber will get you the covers. Honourable mention to @Spencerdl for this. It may take a few scans to get them all.