The geologists tell us that the fossil record here on Earth is a very skewed sampling, and for a wide variety of reasons. Yet, what it seems to show is that life here was one-cell microbial for about 3 billion years, and may have begun almost as soon as liquid oceans formed. That was very shortly after the planet cooled enough to have a solid crust at all (about 1 or 2 hundred million years after formation about 4.5 billion years ago). How all of that life evolution process interacts with changing climate and chemistry, and a slowly-dimming sun, is not well understood. But there it is.
This microbial life left only microscopic fossils, of similar size and form to the odd traces found in the Allan Hills meteorite, which rock came from early Mars as best we can determine. Only in the last 660 million years or so does there seem to be evidence of multicellular life here. This is not conclusive, of course, but it does suggest that microbial life sprouts up quickly and easily in a liquid water environment, while multi-cellular forms may require a time constant on the order of 3 billion years, in relatively benign conditions, to evolve. I could be wrong about that, but that's what the record here seems to say.
We have no reason to believe that the fossil record on Mars would not be as skewed as that on Earth, and probably for the all same reasons. There, like here, the geological record will be hard to interpret, especially any fossil record. What does seem very clear so far is that early Mars was much warmer and wetter, with similar conditions and chemistry to Earth. This is evidenced by the fossil gravel bar conglomerate rock the Curiosity rover just found on Mars.
One of the fossil gravel bar conglomerate rocks Curiosity saw on Mars
Early Mars was quite evidently warm and wet enough to have rivers. That means there were very probably lakes, and maybe even oceans. So, I'd bet real money it had microbial life, just like here. Maybe even the very same sort of life, if the panspermia hypothesis was a factor. The “late heavy bombardment” event of major asteroid impacts (about 3.8 billion years ago) could have spread microbes, or perhaps just their chemistry, between the two planets. That’s also how a rock from Mars arrived here as the Allan Hills meteorite.
The problem is, from what we can tell, that Mars too-quickly dried out (acidifying along the way), and froze up as it lost its atmosphere, for whatever reasons. Apparently this happened a couple of billion years ago. There might have been short warmer, wetter events since then, but that is not certain. So, my hypothesized 3-billion-year time constant for evolving multicellular forms didn't happen on Mars for lack of time, as best we know. Accordingly, I would not bet real money on our finding macroscopic fossils there. But, then, it's only a bet. No one yet knows.
I view any putative macrofossils from any of the Mars lander photos with a jaundiced eye, meaning I have a strong "show-me" attitude about that. There are so many ways for inanimate geology to create forms that look like life fossils, as we know. Putative microfossils on Mars I find much easier to accept, since the climate seems to have been hospitable to Earth-like life for one or maybe two billion years. I do think the NASA scientists who claimed to have found microfossils in the Allan Hills meteorite were very badly mistreated by the scientific establishment. That would be one of Carl Sagan's few mistakes, reacting as hostilely as he did.
Here is what I predict: we may find microfossils of microbial life in sites scattered all over Mars. If we drill deep enough, we may, (I repeat "may") even find living microbes far under the surface, similar to deep-rock microbes found here recently. If we ever terraform Mars, that subsurface life may re-invade the surface and re-colonize it. I rather doubt Martian microbes could sicken us, or that our microbes present a threat to Martian microbes. The chemistry should be different enough after 2-3 billion years' isolation, to prevent any such compatibility, even if they had the same original panspermia source just after planetary formation.
All of that is just my speculation, of course. Enjoy.
PS - this one was published pretty much as-written, as a guest column, in the Sunday 10-14-12 edition of the Waco, Texas, Tribune-Herald.