The Mars Science Laboratory (MSL) has an instrument package capable of making measurements of past and present environmental conditions. The data generated may tell us if Mars is, or ever was, able to support life. However, the knowledge of Mars' past history and the geological processes most likely to preserve a record of that history remain sparse and, in some instances, ambiguous. Physical, chemical, and geological processes relevant to biosignature preservation on Earth, especially under conditions early in its history when microbial life predominated, are also imperfectly known. Here, we present the report of a working group chartered by the Co-Chairs of NASA's MSL Project Science Group, John P. Grotzinger and Michael A. Meyer, to review and evaluate potential for biosignature formation and preservation on Mars. Orbital images confirm that layered rocks achieved kilometer-scale thicknesses in some regions of ancient Mars. Clearly, interplays of sedimentation and erosional processes govern present-day exposures, and our understanding of these processes is incomplete. MSL can document and evaluate patterns of stratigraphic development as well as the sources of layered materials and their subsequent diagenesis. It can also document other potential biosignature repositories such as hydrothermal environments. These capabilities offer an unprecedented opportunity to decipher key aspects of the environmental evolution of Mars' early surface and aspects of the diagenetic processes that have operated since that time. Considering the MSL instrument payload package, we identified the following classes of biosignatures as within the MSL detection window: organism morphologies (cells, body fossils, casts), biofabrics (including microbial mats), diagnostic organic molecules, isotopic signatures, evidence of biomineralization and bioalteration, spatial patterns in chemistry, and biogenic gases. Of these, biogenic organic molecules and biogenic atmospheric gases are considered the most definitive and most readily detectable by MSL.