Acredito que, de fato, use as tags incorporadas no arquivo, que geralmente são chamadas de tags id3, pelo menos para MP3. Eu acho que os arquivos ogg lêem tags id3, mas podem não ler tags id3v2 (versão 2). Alguns softwares gravam um ou outro, ou às vezes ambos.
Tenho notado que leva um tempo para o Nautilus exibir a capa do álbum depois que a pasta é aberta pela primeira vez, mas depois ela é lembrada. Tenho certeza que ele armazena as imagens em ~/.thumbhnails/normal
, mas esse diretório pode ser muito grande, e abri-lo é uma tarefa árdua.
Já ouvi falar de um programa chamado "cover thumbnailer" que faz com que o nautilus funcione melhor; Eu realmente não tentei eu mesmo, no entanto.