O fglrx está realmente disponível no apt-get.
Primeiro de tudo, você precisa ativar o repositório restrito se ele ainda não estiver ativado. Clique aqui para mais informações.
Para instalar o fglrx, execute os seguintes comandos:
sudo apt-get update
sudo apt-get install fglrx
Para referência futura:
Para procurar coisas disponíveis através do apt-get, execute os seguintes comandos:
sudo apt-get update
apt-cache search fglrx
para restringir os resultados, use grep assim:
apt-cache search fglrx | grep fglrx
Além disso, você pode procurar por drivers proprietários disponíveis através do centro de software. Clique aqui para mais informações.
Finalmente, se você insistir em instalar os drivers baixados, você precisará executar os seguintes comandos para instalar os pacotes necessários:
sudo apt-get update
sudo apt-get install build-essential linux-headers-generic