Applying the patch will depend how you are installing the fglrx drivers and will be somewhat distro-specific. Either way, in the step before you compile the drivers, download the patch and place it in the directory (for Debian will be /usr/src/modules/fglrx) where you are about to compile the drivers.
Test the patch by issuing the command
- patch --dry-run -p1 < patch_name.patch
substituting patch_name.patch for the real file of course. You may have to try the -p0 option, so see what works. Reissue the command without the --dry-run to actually apply the patch. After that, compile as usual and install. Note that although the patch applies cleanly, this does not work for me - I still get occasional lockups using 8.21.7 and 220.127.116.11, so I'm still runing 18.104.22.168 until the next ATI release...