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 RPMForge repository and corresponding version matching 10.9 should be there soon. I strongly recommend all of you use this method since it automatically configures the grub config file.
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.