Meu amigo usando uma versão mais antiga do Ubuntu tem o gfortran no Ubuntu Software Center. Eu acho que ele não precisa baixar nada. Já estava lá. Ele acabou de instalar. Mas no meu caso, quando tentei procurar pelo meu próprio Ubuntu Software Center, não consegui encontrá-lo. Acabei de atualizar para o Ubuntu 12.04 LTS. Não está realmente disponível para a nova versão do Ubuntu?
O GFortran aparece no Centro de Software no meu sistema, também 12.04.
Você pode pular o Centro de Software e instalar o compilador a partir do Terminal: inicie o terminal e digite sudo apt-get install gfortran .
Se o terminal apresentar um erro quando você fizer isso, forneça a mensagem de erro.