Before 2.5 to 2Gya, Earth's surface was a chemically reducing environment (evidence includes reduced forms of iron, sulfur, and uranium in rocks before that time). It is believed to have become oxidized as a direct result of photosynthetic life, leading to the precipitation of oxidized iron in BIFs, sulfate deposition, etc., etc.
The surface of Mars is now oxidized (evidence includes sulfates and iron-oxides).
What is the mechanism? Why doesn't the oxidized state require life?
Besides the role of any past photosynthetic life on Mars (see MSalters's answer), excess free oxygen could also have appeared through inorganic processes. Such processes may have been promoted by solar radiation bombarding the atmosphere and surface, releasing oxygen atoms. This is a common theme in what follows.
Space.com gives several possible mechanisms:
Oxygen atoms freed from water molecules, perhaps through the effects of solar radiation on said water molecules, could have been rained down on Mars during storms, possibly creating conditions similar to those that accelerate rusting on Earth.
Solar radiation could have broken down oxygen-containing compounds, leaving oxygen-rich products that attacked the iron (and other oxidizable constituents) directly.
Oxygen from quartz crystals, perhaps again from solar radiation breaking rocks down, could be the culprit.
The space.com site admits that no one really knows; it's possibly a combination of the above mechanisms.
Oxidizing metals may cost a bit of energy, but the net oxidation process is still exothermic. That means that given enough time and oxygen, oxidation is unavoidable.
Life (plants in particular) will make oxygen readily available which accelerates the process, though.
