Use Baking Soda and soap. The method involves taking soap and mixing it with baking soda until you have a scouring powder like solution and then buffing the headlights with that. Rinse the cloth you use, between buffs and rinse clean with fresh water. The link says use Castile Soap and a mild soap is best.
I am not going to explain this method in detail, but in short you buff the headlight clean with the wet and dry sandpaper dampened with the spray bottle water. Then you buff the headlights with the buffering product and apply the adhesive.
The answers above are good, but whatever you do, you need to add a UV coating once you're done. If you don't, you'll be right back where you started fairly quickly. The fogging is due to the breakdown of the original UV coating and consequent fading. I'm not sure what it costs, but I know I'll be buying it when I need to do mine.
As for getting rid of the fading in the first place, toothpaste is good, and professional systems will do a better job. Depends on whether you want to apply the 80/20 principle to this and do it on the cheap, or if you want a real showroom finish.