Overclocking is making a component run faster than it was originally designed to run.

It can be done with a program, like rivatuner, or coolbits, or atitool(?).
It depends on the card, which you use.

Anyway, you just usually increase a slider from the stock core or memory speed a little and test that you don't get artifacts, if you go too far you can get artifacts or crashes.

Yes there can be negative effects, the worst of which would be that the component could fail, and that's no fun. The biggest problem is overheating, so you need good cooling to do this. Usually too high of voltage, or too high of temps. kill a unit. Sometimes more voltage than normal is added to a component to help give it stabiltity at the faster speed.

As long as you haven't gone too far oc'ing, and aren't gettin artifacts or high temps, then it should work in any game.