Por exemplo, o k3b suporta freedb (e MusicBrainz):
Por padrão, o k3b enviará para o freedb quando você adicionar um novo CD.
Se você executar apt-cache search cddb
, obterá uma lista de pacotes que mencionam cddb. Pode valer a pena dar uma olhada em alguns deles também.