An answer I've received elsewhere was that a libertarian society would allow you to sue power companies that output large amounts of C02. I don't like this answer for two reasons:
1) Depending on the type of libertarian society there may not be a court system the power company would agree to be sued in, and they might not obey the decision anyway.
2) Even individual power companies don't emit enough C02 to noticeably affect global C02 levels. Global C02 levels only get measurably affected by the combined output of hundreds of the coal burning plants in the world. You would have to simultaneously sue every power company in the world, which is completely impossible right now and would be even harder still in a world with less centralization.
How would a libertarian political order address this? And more generally, how would it address the problems that arise when a great number of parties each contribute small amounts of pollution into common resources?
If a power company refuses to use courts then it will have a tough time settling disputes where it's the victim. It's going to be a riskier investment which means fewer people are going to invest and those that do invest will invest less. No business is going to get very far and a large business that requires a huge startup cost won't even get off the ground without agreeing to abide by a court's ruling. If it does agree to abide by a court's ruling yet fails to obey then it's violated a contract and can be forced to comply and be charged with the costs of forcing it to comply.
It doesn't matter how much pollution you emit. If you can prove damage is being done to your property and you can measure the amount of pollution emitted then you'll be able to sue proportionally to that damage. You also won't have to sue every polluter on the planet simultaneously. I'm not even sure why you asserted that. You can sue them one at a time. Also, assuming everyone will be a victim then a class action lawsuit can be filed and you won't even have to do much, just sign your name somewhere.
The bottom line is, as long as people value pristine land, clean air and fresh water, there will be a cost associated with spoiling them. Businesses that can avoid these costs will increases their profits, expand and eventually drive the less green companies out of business. The market can handle pollution and has an incentive to do so, as long as we respective property rights and allow victims of pollution to recoup damages from polluters.