We did it with our PPoR rear deck a few years back (2002).
It's merbau, which had faded grey/silver.
I tried to restore the original merbau colour first, by blasting it with the gernie and then cleaning it it with "sickens" cleaner, but it was no good - the silver colour remained, so we decided to paint it.
I used normal Wattyl Solargard. First, coated the edges between the boards with a brush, then rolled the tops of the boards with a heavy roller.
Looked great, but some 7 years later it needs doing again.
The colour was Musgrove. We are currently doing a reno on this house, and the new colour will be Colorbond Dune. We picked this colour as it is lighter, warm ans soft and the house is to be painted a fair bit darker this time, so we wanted a bit of contrast with the house. (see our reno thread at;
http://www.somersoft.com/forums/showthread.php?t=55107 for more updates as we go.)
You want the colour to be a bit lighter to make the deck appear bigger, but not too light that it reflects the sun too much.