First, check your graphics card name and chipset:

sudo update-pciids #optional command, requires internet

lspci -nn | grep VGA

It should report something like this for your graphics card:

01:00.0 VGA compatible controller: Advanced Micro Devices, Inc. [AMD/ATI] RV710 [Radeon HD 4550]

then to check whether your graphics card is fully supported of not check this page on the Ubuntu help wiki.

Unsupported Chips
For the very latest cards, open-source driver support is not always instant. The following cards require a newer version of the driver than what's found in Ubuntu 13.04/Raring's repository, but should be supported by the time Ubuntu 13.10/Saucy is released.

OLAND               Radeon HD 8xxx series

HAINAN              Radeon HD 88xx series

RICHLAND            Radeon HD 8xxxG series

I should say that in newer versions of Ubuntu you don't need to install catalyst control center as it's installed by default and if you try to install a catalyst driver 90% of time you would lose your desktop and taskbar and you'd need to purge fglrx and restore the default version of Ubuntu xorg or fgrlx driver.

installing catalyst control center :

run these commands in terminal

sudo add-apt-repository ppa:makson96/fglrx

sudo apt-get update

sudo apt-get upgrade

sudo apt-get install linux-headers-generic

after that open Software Center and type

legacy catalyst control
or

click on more and click on amd catalyst legacy .

and install fglrx catalyst control center .

Removing:

First go to software & updates and remove ppa:makson96/fglrx or try :

sudo apt-add-repository --remove ppa:makson96/fglrx

sudo apt-get update

Then:

sudo sh /usr/share/ati/fglrx-uninstall.sh

sudo apt-get remove --purge fglrx fglrx_* fglrx-amdcccle* fglrx-dev*

Note: ignore any errors you may have got form running the first 2 commands.

Remove your xorg.conf file

sudo rm /etc/X11/xorg.conf

Re-install xorg

sudo apt-get install --reinstall libgl1-mesa-glx:i386 libgl1-mesa-glx:amd64 libgl1-mesa-dri:i386 libgl1-mesa-dri:amd64 xserver-xorg-core

Configure xorg

sudo dpkg-reconfigure xserver-xorg

Reboot:

sudo reboot

Try this for newer kernel :
http://www.thefanclub.co.za/how-to/ubuntu-amd-catalyst-install