Be sure to scroll down... there may be more than one question on this page!
You could rent a power washer, but there is risk of damage to the wood by the high-pressure spray! I've seen decks destroyed by over-enthusiastic handymen, so if you rent one keep the nozzle at least a few feet from the deck. Ask the rental agent for their recommendations.
Aside from using a power washer, at the least you need a product with bleach as the active ingredient. Olympic and Cuprinol both have strong bleach-based deck cleaners. If you have tried either of these without success, you can go really hardcore and use TSP and bleach. There is a TSP article on the website.
You can also try JOMAX from Zinsser. JOMAX is mixed with bleach and water. It activates the bleach to make it kill that mildew faster and more effectively than a bleach/water/detergent mix alone… while special detergents clean without scrubbing in most cases. I've gotten results similar to a powerwasher on all but the most crusty dirt… without having to rent one!
There are also acid-based deck cleaners. These are also effective cleaners, but do not kill mildew as well as bleach. Also, acid cleaners are not compatible with some deck sealants and stains. If you have chosen a stain or sealer, read the label on the product for cleaning product recommendations or exclusions!
Sorry, but despite what the cleaners may say you will definitely have to scrub, especially if there is heavy moss! Though some of the cleaning products claim no-scrub cleaning, this ain't necessarily so! So have a scrub brush (the type with a pole) handy to work on the algae AFTER it soaks for a few minutes in the cleaner. You might want to let the surface dry and reapply the cleaner a second time to the most difficult areas.
One useful tip... you might find that the treated wood has a "greenish tinge" after extensive cleaning and scrubbing that just won't come off. Don't worry about it... it will usually disappear after the wood dries out!