XMMS + CDDB, как?

Не совсем понял.

1. Плагин CD Audio Player штатно умеет брать инфо с CDDB (или FreeDB, как попросите) и CD Index. Просто надо зайти в его настройки (если такого плагина нет, скачать и поставить).

2. А вот если вопрос касался mp3, то смотрите плагин CoverViewer. Если играемая вещь не является очень редкой и хороший коннект (на момент первого проигрывания композиции, потом обложки кэшируются), то при проигрывании композиции в спецокошке будет показываться обложка диска (официального), на котором была такая композиция. Насколько я понял, можно и свои обложки добавлять.