Alright, let me try a completely different take on this.
I'm assuming that by libertarianism we mean anarcho-capitalism, since a minarchist libertarian society can still justly enforce carbon taxes and the like as CO2 emissions are a form of harm/aggression against others.
Just a few weeks ago, the governments of the world managed to make significant progress toward addressing the climate change issue in Durban, laying the foundations for a cap-and-trade agreement to be made in 2015 and to take effect in 2020, potentially including commitments by the US, China and India. Now, international law respects the sovereignty of nations, so theoretically any country could pull out and keep polluting, and setting up the treaty to shut down if any party reneges on its agreements, while a valid strategy for bilateral agreements, would not be viable in this case. So what would be in place to dissuade polluters? Economic sanctions - essentially everyone would put tariffs on their goods. With that penalty in place, it's in everyone's interest not to pollute.
But why would anyone put tariffs on goods? It's well known that tariffs introduce economic inefficiency and ultimately hurt more than they help due to deadweight loss, so why would anyone take the hit for themselves to punish others? Two factors are at play. First, the specific mechanism of a tariff has the very attractive property that the disincentive to trade with the cheater scales linearly with the tariff (by definition) but the deadweight loss scales with the square (since with a 10% tariff everyone with less than a 10% profit margin has to stop trading, losing out on approximately 5% profit, but with a 20% tariff everyone with less than a 20% profit margin (about twice as many people) has to stop trading, losing out on approximately 10% profit - see here:
http://en.wikipedia.org/wiki/Deadweight_loss and notice how the harm is in the form of a triangle), so it's worth it for large players like the US to impose reasonably small tariffs that carry a medium amount of push at very low cost. Second, tariffs can be enforced recursively - if anyone refuses to implement punitive tariffs, the WTO might decide to implement a punitive tariff against them, and everyone would be similarly pushed to implement that punishment as well.
So how would all this translate into a libertarian society? All that the previous explanation required is the existence of powerful market players that are motivated by a large number of people's welfare and that has control over a powerful economic output. The lever of control does not have to be a tariff - taking a model of a country as an atomic unit (stay with me here for just one second libertarians, I know why that perspective is so philosophically wrong, but it's useful here), a tariff is really a country stealing from itself and cutting down on a certain one of its actions. A person or institution can, instead of a tariff, implement a partial boycott. To illustrate the principle, an business might reduce its electricity consumption by 10%, cutting out only that portion of its usage that provides only a small marginal benefit over not using electricity (eg. turning off the lights when it's not too inconvenient) but still pushing down his demand for electricity by a considerable amount. But organizations enacting such measures do not have to be governments with monopolies over large land areas. Possibilities include:
* A corporation, choosing to support voluntary pro-climate moves as a side benefit to its customers and workers
* A cooperative democratically voting to support such measures
* A voluntary mutual aid society
* A health or home insurance company seeing an interest in reducing how much it will have to pay to deal with the diseases that global warming helps spread or hurricane activity
Such large groups would agree on a treaty to reduce their emitting activities, and also reduce their use of products from businesses outside of the treaty. With large companies being more willing to work with pro-environmental players, a degree of enforced environmentalism trickles down into medium sized businesses and groups and even small businesses as well.
And so far all this assumes purely materialistic self-interested agents. Once you add social peer pressure, environmentalists who actively desire seeing the earth not being polluted just as strongly as we desire our homes not having dirt all over the place, and other psychological factors the scale tips even further.