The immediate task facing exopaleontology is to define a strategy to explore Mars for a fossil record during the decade-long exploration program that lies ahead. Consideration of the quality of paleontological information preserved under different geological conditions is important if we are to develop a strategy with broad applicability. The preservation of microbial fossils is strongly influenced by the physical, chemical, and biological factors of the environment which, acting together, determine the types of information that will be captured and retained in the rock record. In detrital sedimentary systems, preservation is favored by rapid burial in fine-grained, clay-rich sediments. In chemical sedimentary systems, preservation is enhanced by rapid entombment in fine-grained chemical precipitates. For long-term preservation, host rocks must be composed of stable minerals that are resistant to chemical weathering and that form an impermeable matrix and closed chemical system to protect biosignatures from alteration during subsequent diagenesis or metamorphism. In this context, host rocks composed of highly ordered, chemically stable mineral phases, like silica (e.g., cherts) or phosphate (e.g., phosphorites), are especially favored. Such lithologies tend to have very long crustal residence times and, along with carbonates and shales, are the most common host rocks for the Precambrian microfossil record on Earth. Although we make the defensible assumption that Mars was more like the Earth early in its history, clearly, the geological and historical differences between the two planets are many. Such differences must be carefully considered when adapting an Earth-based strategy to Mars.