New Wooden decking. To stain or not to stain
I'm not sure what preservative-treated means. [Edit: lower in the page it specifically reads "pressure-treated".] Around here, pressure-treated lumber is soaking wet and not suitable for stain/sealer until it's dried at least an entire season. 

If it's truly kiln-dried, you're free to apply a stain/sealer at any time. To preserve color and prevent surface degradation, sooner is better.