Debian

This is a quick guide and it needs a rewrite. I only wrote this because there was no Debian way till now. But it works

This is the way I prefer but it's not the best way. Download one of the .rpm packages. Than convert it to an .deb package with alien.
alien -d fglrx-*.rpm
Now install it with
dpkg -i --force-all ./fglrx_*.deb
The * replaces the version string from the packe. After that you must change to /lib/modules/fglrx/build_mod/ where you have to execute sh ./make.sh . This will build the kernel module. At last we go to the parent directory cd ../ and execute sh ./make_install.sh . Now you can configure your X-Server.

Why isn't it a good way?
The --force-all parameter ignores all errors from the packagesystem. This is always the case, because there's a conflict with one package from the X-Window system. When you update your Debian system and there is an update for the X-Server, than apt will stopp the updateprocess. Now you need to look which package stops the updateprocess. Go to /var/cache/apt/archives/ and than do dpkg -i --force-all broken-package where broken-package have to be replaced by the package that interrupts the updateprocess. Now you can finish updateing the rest of your system as you did before. But after that you have to reinstall the fglrx package like before.