You've probably found it, but just below the penguin at the "Linux currently offline" listing is an Ubuntu icon with "Ubuntu UFO:AI at PlayDeb" next to it. The PlayDeb link takes you to their page, their install instructions are through a link at the bottom right of their "Welcome" page.
I had difficulties with it (looks now like I didn't simply download and install the PlayDeb package in step one. The post
http://ufoai.ninex.info/forum/index.php/topic,6112.msg48576.html#msg48576 reminded me) but I didn't keep precise notes, I think I was mainly just expecting it to work like it had in earlier versions of Ubuntu.
After their install instructions, in Firefox clicking the "Install this now" link should offer to open the Ubuntu Software Center, it should open with the details open so you can just click "Install" to the right.
If that doesn't work, after the PlayDeb install instructions, there should be in Ubuntu Software Center a "GetDeb" category you can get to by clicking the dropdown arrow next to the "All Software" icon, then you can type "ufo" in the search box and install it there (the main listing is "UFO: Alien Invasion - build your team and stop the aliens" it has just the word "ufoai" under it). Searching for ufo before selecting the GetDeb category doesn't find it.
Also, if those don't work, their install adds a repository and you can add UFO:AI (ufoai) through a package manager like Synaptic.
If you prefer terminal commands, after doing "sudo apt-get update" in their instructions, you should be able to do:
sudo apt-get install ufoai