For Ubuntu you can simply run:

http://kanotix.com/files/install-fglrx-debian.sh