Microorganisms preserved within the permafrost, glaciers, and polar ice sheets of planet Earth provide analogs for microbial life forms that may be encountered in ice or permafrost of Mars, Europa, Callisto, Ganymede, asteroids, comets or other frozen worlds in the Cosmos. The psychrophilic and psychrotolerant microbes of the terrestrial cryosphere help establish the thermal and temporal limitations of life on Earth and provide clues to where and how we should search for evidence of life elsewhere in the Universe. For this reason, the cold-loving microorganisms are directly relevant to Astrobiology. Cryopreserved microorganisms can remain viable (in deep anabiosis) in permafrost and ice for millions of years. Permafrost, ice wedges, pingos, glaciers, and polar ice sheets may contain intact ancient DNA, lipids, enzymes, proteins, genes, and even frozen and yet viable ancient microbiota. Some microorganisms carry out metabolic processes in water films and brine, acidic, or alkaline channels in permafrost or ice at temperatures far below 0 degree(s)C. Complex microbial communities live in snow, ice-bubbles, cryoconite holes on glaciers and ancient microbial ecosystems are cryopreserved within the permafrost, glaciers, and polar caps. In the Astrobiology group of the NASA Marshall Space Flight Center and the University of Alabama at Huntsville, we have employed advanced techniques for the isolation, culture, and phylogenetic analysis of many types of microbial extremophiles. We have also used the Environmental Scanning Electron Microscope to study the morphology, ultra-microstructure and chemical composition of microorganisms in ancient permafrost and ice. We discuss several interesting and novel anaerobic microorganisms that we have isolated and cultured from the Pleistocene ice of the Fox Tunnel of Alaska, guano of the Magellanic Penguin, deep-sea sediments from the vicinity of the Rainbow Hydrothermal Vent and enrichment cultures from ice of the Patriot Hills of Antarctica. The microbial extremophiles recovered from permafrost, ice, cold pools and deep-sea sediments may provide information relevant to the question of how and where we should search for evidence of extant or extinct microbial life elsewhere in the Cosmos.