Imagine if you were to drop a rover into the Sahara desert and drive it around - how likely is it that you'd find a fossil?
They are rare on Earth, except in certain types of rock. If Mars has the equivalent of chalk cliffs or shale deposits we may suddenly hit on a vein with loads of fossils.
But the other thing is that the easiest fossils to spot are the ones for multi-cellular creatures. Those only evolved half a billion years ago - most of them anyway. So they may never have evolved on Mars.
If so we may be looking for fossil microbes. And those are very hard to identify and easily confused.
Instead, then we will look for fossil organics as the primary goal for past life. There, Mars has advantages, with a cold climate that can preserve organics in a "deep freeeze" for billions of years. But any organics that have been on the surface all that time will be utterly destroyed, reduced to water vapour and other gases mainly, by cosmic radiation and solar storms. It's an exponential process, so over a few millennia, or a few hundred thousand years, nothing much happens. But over hundreds of millions of years, and billions of years, then it disappears very rapidly. Even many meters, millions of tons, would be reduced to almost nothing over that timescale.
So, we are looking for conditions where the organics may be preserved underground, then exposed to the surface in the last few million years. Or we need to drill, ideally to ten meters or more. That's why ExoMars plans to drill to a depth of 2 meters. There is organics on the surface, Curiosity proved it, but it is almost certainly from meteorites, indeed the puzzle is that we didn't find it sooner, as Mars gets so many meteorites it should have organics everywhere on its surface, in small quantities. Even taking account of the long term destruction by cosmic radiation. But it doesn't. Something is actively destroying it. Perhaps the perchlorates.
So we need ancient organics. But again - organics from the past also may be deposited by meteorites, or formed by inorganic processes. So we need ancient life based organics. And remember, if you have a deposit of organics, there may be creatures that eat it. Also, Mars has had many floods, and these would tend to wash out the early deposits below the surface - in many places its surface is very porous, "gardened" by meteorites to a considerable depth
So, they are looking for clays, or salt deposits, likely to preserve ancient organics. And then - ExoMars anyway plans to drill, and to search for life "in situ". I think it has the best chance of finding past life on Mars.
The successor for Curiosity will just collect some samples with organics from the surface. Unless life is very common on present day Mars or past life is very easy to find, I think many exobiologists would say, it's unlikely to find signs of life. It is perhaps more geologically than astrobiologically motivated despite their stated aim that they hope to resolve questions about life on Mars.
We may find fossil life though. One astrobiologist thinks she has detected signs already:
The problem is, that fossils of ancient microbes tend to be very controversial - we may eventually prove that some of the things Curiosity has photographed are signs of life. Maybe future astrobiologists will be able to go back through the photographs and see fossils everywhere. But it will take a lot of work to prove that any of the things spotted really are fossils.
We may also find present day life, as there are several ideas for potential present day habitats on Mars now. None of them proved but some are rather promising.