debian has also fglrx install files in the repo...
search in kpackage "fglrx"
the driver if you use ubuntu 9.04 there is the radeon and radeonHD driver allready in it...with super nice 2D performance..
ubuntu 8.10 automatikly installs the fglrx in the hartware menue..
and the offizial file is not so complex you need to give it a chmod "executable" and then you musst start the .run
linke this: "./ati-driver-installer-9-1-x86.x86_64.run"
as root in a shell... best works with "init 3" bevor. .
witch kind of linux distro do you use ?