I did one of those headlight restoration packages on my wifes Hyundai about three months before we traded it. Her lights had gone translucent (couldn't even see the bulbs through the haze) and yellow.
It took about half an hour with the water, abrasive and patience but they came out almost as clear as cheap replacements. I'd say it took care of 90% of the hazing, apart from the little bits that didn't get done and it only cost $10-15.
Just be careful with the optical polish, it is WAY runnier than you think it will be and mine came in little ketchup packets that blew the stuff all over the hood
She got it at Wal Mart I think, it came in a fat silver envelope.