Essa é uma dica simples, mas muito útil. Para ativar a gravação de outros formatos, além do wave, como CD de Audio no K3b, basta apenas instalar os codecs extras no Ubuntu e derivados:

sudo apt-get install libk3b6-extracodecs

Com isso você pode clicar em New Audio CD Project (Novo Projeto de CD de Áudio) e selecionar suas músicas mp3 para gravar e ouvir normalmente em qualquer aparelho com formato mp3 suportável.