A maneira mais fácil é usar o X-Swat PPA . Os drivers da AMD aqui são atualmente uma versão atrás dos lançados pela AMD (eles são baseados no Catalyst 10.11 ao invés de 10.12), mas funcionam perfeitamente e naturalmente instalam (e atualizam) sem problemas.
Se você quer a versão mais recente do Catalyst, o instalador do AMD é muito bom, a menos que você use um kernel não suportado; A AMD ainda não suporta oficialmente versões de kernel maiores que 2.6.35. Supondo que você esteja usando o Ubuntu 10.10 com o 2.6.25, você não terá problemas.
Caso contrário, veja meu tópico aqui: link . Isto dá detalhes sobre o patch do Catalyst 10.12 para uso nas versões de kernel 2.6.36 e 2.6.37.