The best option: FGLRX - Proprietary drivers, downloaded directly from ATI and compiled yourself!
In addition to obysr's answer, I always had trouble installing using the Additional Drivers. Below are a bunch of commands I used to build and install the drivers directly from the AMD website.
sudo apt-get install build-essential cdbs fakeroot dh-make debhelper debconf libstdc++6;
sudo apt-get install dkms libqtgui4 wget execstack libelfg0 dh-modaliases;
sudo apt-get install linux-headers-generic xserver-xorg-core libgcc1;
sudo apt-get install ia32-libs lib32gcc1 libc6-i386;
cd /usr ; sudo ln -svT lib /usr/lib64;
cd ~/; mkdir catalyst12.4; cd catalyst12.4/
wget http://www2.ati.com/drivers/linux/amd-driver-installer-catalyst-13.1-linux-x86.x86_64.zip;
unzip ./amd-driver-installer-catalyst-13.1-linux-x86.x86_64.zip
chmod +x amd-driver-installer-catalyst-13.1-linux-x86.x86_64.run;
sudo sh ./amd-driver-installer-catalyst-13.1-linux-x86.x86_64.run --buildpkg Ubuntu/precise;
sudo dpkg -i fglrx*.deb;
- Copy and paste these into a file.
- Save as installATI without an extension on your Desktop (important!).
- Right click on the file and select properties.
- Select the 'Permissions' tab and tick the 'Allow executing as a program' textbox.
- Close that window.
- Press Ctrl + Alt + T to open a terminal.
- Type
sudo ./Desktop/installATI
and enter your password