Hi Carie, hire a pressure cleaner and give it a good wash, this will also blow off any loose paint. You may have to go over any badly flaking places, if any, with a wire brush.
I live in Australia and don't know what brands of paint you have over there, but you should paint it, not stain it, or you will be creating a lot more work for yourself, down the track.
Use an acrylic (water based) paint, can you get Solar guard, or Weather shield, over there?
it must be an exterior paint, that shouldn't need an undercoat. How-ever, you will probably need at least three coats.
It is usually best to use the best paint, the difference in price is minimal, you will probably paint it for a couple of hundred dollars at the most. A 20 litre can goes a long way.
Use Dulux, if you can, it is one of the best.
Cheers
