The building blocks of life as we know it, including amino acids, nucleobases, and sugars, were synthesized early in the history of the solar system in space, in processes likely common throughout the universe. After delivery to habitable worlds, such building blocks may have biased independent origins of life, if they occurred, towards similar solutions. For example, nucleic acids or their cousins may serve as a common physical basis for heritability and evolution. Nucleic acid-based informational polymers (IPs) are even more likely for any life that may exist or may have once existed on Mars, due to extensive meteoritic transfer between Mars and Earth. Until recently, it was infeasible to build a device capable of extraction, library preparation, and sequencing that is compatible with the severe mass, power, and volume restrictions of planetary exploration. This is now changing with the advent of ultra-portable single molecule sequencing technologies. I describe progress in developing the Search for Extra-Terrestrial Genomes (SETG), including simulating Mars in the lab, sampling environmental analogs of Mars, distinguishing between putative Martian life and any forward contamination from Earth, and working to extend our capabilities to non-standard bases and polymers.