If a person were to die on the Moon or Mars, would the body decompose? There wouldn't be enough oxygen for any bacteria to decompose the body, right? Not to mention, the radiation of space might kill off most organisms on it. So would it decompose, given millions of years?
Space, as Randall notes, is really dry. Mars, (recent discoveries notwithstanding) is not much moister.

In these conditions, bodies mummify. 

The microbes that live in you, wouldn't survive the freezing, dessication and radiation. There is no real upper limit on how long a mummified body could exist in space. There would be nothing to cause the body to change, and so it would remain. There would be a slow breaking down of surface proteins, due to UV light, and eventually micrometeorites would erode the body, but these processes would take many millions of years.