Aqui está um plugin nautilus que faz isso.
Instruções:
sudo aptitude install python-nautilus
wget http://seemanta.net/code/Nautilus_plugin/add-to-rhythmbox_V02.py \
-P ~/.nautilus/python-extensions
killall nautilus
# Navigate to your music folder again, right click, add to play queue