Fedora 13 Installation Guide
ATI's latest Catalyst 10.9 now well supports Xorg-server 1.8.
Pre-built .rpm packages should be in the non-official RPMFusion repository and corresponding version matching 10.9 is now out there. I strongly recommend all of you use this method since it automatically configures the grub config file and configure DKMS settings.
An alternate way is, to download the .run installer, run it using root privileges, follow the instructions on the screen and reboot afterwards. However, you must manually add a 'nomodeset' parameter in the grub entry, or the computer will hang with a black screen after plymouth bootscreen due to a conflict against kernel modesetting and fglrx.