Wow, cool plugin.. never even seen it before. Installed
Heres what you do. Download the package to /home. Open with your archive manager and extract the folder to /home. Then open nautilus as root:
Open another instance of Nautilus (or use split view) and copy the folder you extracted from the tarball. Then go to the root instance of nautilus and right click>paste. After done, close and reopen rhythmbox. For some reason, everytime I add a plugin, Rhythmbox never works the first time, so I have to close it and reopen again.
gksu nautilus /usr/lib/rhythmbox/plugins
Plugin is working for me..
**EDIT** Make sure you go to Edit>Plugins and enable the "Album Art Search Panel" checkbox in order to use.