My friend using an older version of ubuntu has gfortran in the Ubuntu Software Center. I think he did not need to download anything. It was already there. He just installed it. But in my case, when I tried searching for it my own Ubuntu Software Center, I couldn't find it. I just upgraded to Ubuntu 12.04 LTS. Is it really not available to the new version of Ubuntu?
GFortran appears in the Software Centre on my system, also 12.04.
You can skip the Software Centre, and install the compiler from the Terminal: launch the terminal, then type
If the terminal gives you an error when you do this, please give us the error message.