One solution is to introduce artifical greenhouse gasses, such as CFCs, which although proven safe for humans to breathe, cause serious problems with global warming, and our Ozone, or the more ozone friendly, and UV blocking, but possibly science-fiction class of PFC chemicals. Kim Stanley Robinson claims that about a thousand facotries about the size of a volkswagon could be designed to synthesize these chemicals on Mars, and warm the planet up to a toasty Himalaya's type climate.

That's all well and good, but what kind of space program would ever launch a thousand volkswagons to Mars? Not ours, that's for sure.

So, we've got a potentially fictional terraforming chemical, and a definite pipe drea of a delivery system. This idea could be really great if we tossed in some GM Magic.

As I figure it, CFCs are a lot less complex than a lot of the chemicals we already use bacteria and such to synthesize. So, if we splice some genes to produce this sort of gas into a cyanobacteria, we can throw that good old blue green algae all over Mars...

and it will freeze, dehydrate, and die, because algae grows best in water. What we need is a tougher kind of plant.

Lichens might make a better host for our GM genes. Composed of algae and fungus (as well as other things somethimes) there are actually multiple organisms we could fiddle with, in case one doesn't work as well as the other. The symbiotic nature of the organism allows lichen to dwell in drier, colder environments with much thinner atmospheres. Some lichens are also able to leech oxygen, and other useful chemicals from the substrate they grow on.

The durability of lichens make these organisms much more likely to survive on Mars. Also, a "volkswagon" sized payload of lichen could be sent to Mars, and grow there, increasing the returns of such missions exponentially until Mars is hellishly hot and... um, maybe we better remember to include some suicide genes.

Oh well, if you want a terraformed world, you've got to break a few planets I guess.