Here we review published studies on the abundance and diversity of terrestrial rock-hosted life, the environments it inhabits, the evolution of its metabolisms, and its fossil biomarkers to provide guidance in the search for life on Mars. Key findings are (1) much terrestrial deep subsurface metabolic activity relies on abiotic energy-yielding fluxes and in situ abiotic and biotic recycling of metabolic waste products rather than on buried organic products of photosynthesis; (2) subsurface microbial cell concentrations are highest at interfaces with pronounced chemical redox gradients or permeability variations and do not correlate with bulk host rock organic carbon; (3) metabolic pathways for chemolithoautotrophic microorganisms evolved earlier in Earth's history than those of surface-dwelling phototrophic microorganisms; (4) the emergence of the former occurred at a time when Mars was habitable, whereas the emergence of the latter occurred at a time when the martian surface was not continually habitable; (5) the terrestrial rock record has biomarkers of subsurface life at least back hundreds of millions of years and likely to 3.45 Ga with several examples of excellent preservation in rock types that are quite different from those preserving the photosphere-supported biosphere. These findings suggest that rock-hosted life would have been more likely to emerge and be preserved in a martian context. Consequently, we outline a Mars exploration strategy that targets subsurface life and scales spatially, focusing initially on identifying rocks with evidence for groundwater flow and low-temperature mineralization, then identifying redox and permeability interfaces preserved within rock outcrops, and finally focusing on finding minerals associated with redox reactions and associated traces of carbon and diagnostic chemical and isotopic biosignatures. Using this strategy on Earth yields ancient rock-hosted life, preserved in the fossil record and confirmable via a suite of morphologic, organic, mineralogical, and isotopic fingerprints at micrometer scale. We expect an emphasis on rock-hosted life and this scale-dependent strategy to be crucial in the search for life on Mars.