I'm not so familiar with the X1800 since I have an X1900, but I think the process is still the same.
Here is a step-by-step on how to oc that badboy:
1) Use CAT 6.3 (if you want) display drivers only which can be found on ATI's website. Not sure if the Chuck patch gives any problems with ocing but I imagine it wouldn't. Reboot when prompted.
2) Install ATI Tray Tools and make sure to disable overclocking. An option will appear when you're doing the install that allows you to uncheck a box for overclocking.
3) Install ATI Tool Beta 14
4) Disable the ATI Smart and ATI Hotkey services. You can find them under Control Panel -> Administrative Tools -> Services (with Classic View) or Control Panel -> Performance and Maintenance -> Administrative Tools -> Services (using Category View). You can disable them by right-clicking on them, going to Properties, and then under Startup Type choose disable and apply. After disabling both services, reboot your computer.
5) You should be able to start ocing now. In ATI Tool go to the Settings tab and than to Voltage. Just try and find your max oc on stock volts which is 1.4 or 1.425V (I forget which) on the core (first of the four adjustments) and leave the rest the same. When finding your max oc, adjust the core up in 10MHz increments and test with the built in Artifact Scanner in ATI Tool. I usually let it run for 5+ minutes with no errors before I bump the core up again. You'll start seeing artifacts in the spinning, furry, cube and it will also inform you that you've gotten errors.
Now, you want to put the core back to stock and test the memory the same way. Once you've found the max of the memory, you can find the max of the core and meme together which is generally a little lower than either separately.
You'll get very close with the Artifact Scanner in ATI Tool but just be aware that the more intense games out (FEAR, Oblivion, etc.) might cause artifacting that the Scanner couldn't find. I had to bump my volts a tad to get FEAR to be artifact free.
This is the method I've used anyway, thanks to Elfear. I've had a little trouble with mine due to the voltage regulators. The only application I'm having trouble with running my OC's at is Oblivion, but I've heard that that game doesn't do well with overclocked components. Good luck and I hoped that will help.