Are there fossils on Mars? The Christian Science Monitor

A careful study of images taken by the NASA rover Curiosity has revealed intriguing similarities between ancient sedimentary rocks on Mars and structures shaped by microbes on Earth. The findings suggest, but do not prove, that life may have existed earlier on the Red Planet.
The photos were taken as the Mars rover Curiosity drove through the Gillespie Lake outcrop in Yellowknife Bay, a dry lakebed that underwent seasonal flooding billions of years ago. Mars and Earth shared a similar early history. The Red Planet was a much warmer and wetter world back then.
On Earth, carpet-like colonies of microbes trap and rearrange sediments in shallow bodies of water such as lakes and coastal areas, forming distinctive features that fossilize over time. These structures, known asmicrobially-induced sedimentary structures (or MISS), are found in shallow water settings all over the world and in ancient rocks spanning Earth’s history.