There are two different sets of recommendations depending on the type of decking:
For a pressure treated lumber deck:
To start with, you will want to remove the current flaking varnish, otherwise any treatment you give the wood will not apply consistently, and in any case will just sit on top of the varnish, so strip it all with a good paint stripper. An oxygen based one can brighten up the wood quite considerably as it gets rid of mildew.
Wash the wood - a power washer is pretty good for this.
You may also need to sand - this helps take the surface to a consistent level, and can remove splinters that may have been left after the paint stripping and washing.
Then use an oil based stain if you want to go for long term wood protection - this will get right into the pores in the wood. Ensure the deck is dry first - a couple of days of sunshine and no rain will help the uptake of stain. Make sure the stain is semi-transparent if you want the lustre of the wood to show through.
Varnish and paints should not be used - You have seen what UV rays do to varnish.
For a hardwood deck:
You will not want to use such active chemicals to strip the paint, and in fact you may wish to just use a sander to avoid chemical damage to the wood.
An oil based stain will not be as useful either, so you may want to go with a more resin based stain, or even just re-varnishing it.