[ElkGroveDan]

Well I used the fish as an example, but clearly there are fossil shapes that could excede the boundaries of geologic explanation.

I don't think it would be unreasonble to imagine multiple appendages or fins in an aqueous environment, or perhaps some sort of spinal structure, assuming life on the alien location had enough time to evolve that far.

[brownsfan]

I think you're getting carried away here. Big news would be that there is, or was, water on Mars. I suspect that's what they've found. Going beyond that, there is a lot of chatter on space.com about a Viking Lander scientist who claims his test in 1976 found evidence of microbes on Mars. I'm guessing it's a bit early in the rover mission to say they've found microbes. But, that's as big as it will get. I'd wager huge dollars that there are no complex life form fossils. But the idea does get the blood flowing!
Even if it is the discovery of microbes, that's going to be a major event in history. It will be alongside Copernicus in terms of discovery, and our re-evaluating ourselves and our role in the universe!
Exciting stuff.