I bought a house last year with a cedar deck that had turned gray, and was covered in the lousy Thompson's stuff.
First, I power washed (from a distance @ ~1700 PSI) and stripped off the dead layer (with the grain, not against it, you don't want to make the wood fluffy).
Next, I did a mild corrosive wash with a Wood Brightener I ordered from Ontario. I would have to double check the brand (it's in my garage), but it worked amazingly well. I had seen it recommended on a forum somewhere. A good hard scrubbing with this stuff, then a rinse.
Lastly, I applied this stuff, twice:
http://www.cil.ca/Products/WoodcareP...ksFencesSiding
The deck looks awesome, and even though it's been a year, it looks like I stained it yesterday.