I have not seen a guide on this around here, so I am making a quick one. Please feel free to make any additions, corrections, etc.
The first step before overclocking is determining your base temps. You want the temp under full load, so run furmark stability test, homepage here.
After six minutes, the temps will be pretty much maxxed out. The most a GPU can get to is typically 110C, but you really do not want them to go over 90C. Remember that it is vcore increase that produces increased temps, not necessarily increased clock speeds.
Now for the fun part.
For small overclocks, you can use ATI overdrive, built into Catalyst control center. To do this, fire up CCC, go to advanced mode if you haven't already, then go to the overdrive tab. You will notice that everything is greyed out if this is your first time using it. Do not worry, this is normal. Click the picture of the lock. An EULA will pop up. Once you have agreed to it, you will notice that you can now use overdrive. Yay! Simply use the sliders, then click apply to adjust clocks. It is best to go up about 5 MHz at a time on the core and 10 at a time on the memory, running furmark, or another stability test each time until it artifacts, then backing the clocks down a bit. If you want, you can also increase fan speed to keep temps lower.
If you want higher overclocks, there is MSI Afterburner. There are a few advantages to this over ATI overdrive. The most obvious is that it supports higher clock speeds. The second is that it allows voltage tweaking on cards that support it. The third is that you can create custom fan graphs, so your fan will only get loud while at high temps. It also has monitoring programs built-in, and a lot more, but this is just the basic stuff. To overclock with MSI Afterburner, you do the same as before, moving sliders in small increments, stress testing each time. Except this time, when you artifact, assuming temps are safe, and your card supports it, you can enable voltage control, and bump the voltage a little bit. This will allow a higher stable core clock. At this point, as far as I know, there are no cards that support vmem tweaking out of the box, but there are volt mods for this if you really want it. First, check if the core voltage slider is enabled. If so, you may skip until the part about vcore adjustment. If not, you must first check in settings to make sure voltage tweaking is enabled. If it isn't then enable it. If it still doesn't work, then you must open the following file: msiafterburner.cfg in the afterburner installation folder. Changer EnableUnofficialOverclocking = 0 to = 1 and restart your PC. If it still didn't work, you may be out of luck, though I have heard of some people having luck flashing their cards to MSI or ASUS BIOS.
voltage tweaking: Increasing the core voltage allows you to overclock higher, but it also means higher temps. If you increase the vcore, do it in very tiny increments and watch your temps carefully.
For nVIDIA cards, the best overclocking software to use is Rivatuner. Go to system tweaks, then overclocking, and you will see overclocking options. Check the box to allow overclocking. For nVIDIa cards, the overclocking process will be similar to the above, except there will now be three sliders, core, shader, and memory. Core and shader should be linked together by default, but you should unlink them for better tuning. Adjust everything slowly, probably 5MHz at a time on core, 10 on memory and shaders. Test stability between every tweak and watch carefully for any artifacts.When you do begin to see them, back down your clocks a bit. Since all modern nVIDIA cards do not support voltage control, you would need a hard vmod to adjust it.
Congratulations, you have now overclocked your graphics card!
Why are my clock speeds showing up significantly lower than what my overclocking program says?
Well, modern Graphics cards have two separate clock speeds, one for 2D (at the desktop) and one for 3D (Games). If you fire up a game, or furmark, you will see that the clocks go up to what you set.
Is there any way to flash my card to a different card's BIOS, to turn it into a better card?
Well, yes and no. This trick currently works for only three cards that I am aware of, HD 4860 to 4890, 4870 x2 to 4870 x2 top, and 5850 to 5870. Also, the disabled shaders are laser cut, so there is no way you are getting them back. All it will do is increase the clock speeds, and overclocking potential, assuming you are limited by the card's BIOS, but by voltage or by heat or the chip.