Changing freewheel singlespeed cog
You need a freewheel remover tool which fits the cog you have. Park Tool makes a lot of these, and has some excellent directions for replacing the freewheel here (and in the unlikely event you can't get a remover tool which works, there is a destructive way of removing freewheels, which is a last resort - we will assume you have the tool). Sheldon Brown also has some directions here. 

Roughly speaking what you'll do is you'll look at the freewheel you have, buy the appropriate freewheel remover tool and a large crescent wrench or similar. Then, you'll put the freewheel remover tool into the notches on the freewheel and snug up your quick release skewer / axle nut to hold it in place. Then, using a crescent wrench or vise, turn counterclockwise for 1 turn of the freewheel remover tool, and then remove the QR skewer / axle nut. Then, use the crescent wrench / vise to remove the freewheel the rest of the way (still counterclockwise). 

Installing the new freewheel is straightforward - apply anti-seize, thread it onto to the mounting threads (take care not to cross thread) all the way, and you're done. It will feel weird at first, but as you ride more, the freewheel will tighten down on the hub. You can also use a chain whip (clockwise) to tighten it down all the way if you want, before you ride (this will prevent the weird feeling).