You know what? Screw global warming for now. How would a libertarian society handle the current level of water poisoning? Fish are dying out, more and more beaches fill with algae, rivers are full of waste (from detergents to artificial manure) etc. None of these things visibly influence businesses that make the mess. How free should this market stay?
The standard answer is if the river is owned, then the owner(s) of the river will have the right incentives to keep it unpolluted. See, for example: http://www.cato.org/pubs/journal/cj1n2-6.html
If you care about clean rivers, then buy them (or donate money to an organization that buys them; the Nature Conservancy is one of my favorite charities).
It is the Chinese government's river, not the free market's, why are they tolerating all the pollution?
Global Warming and air pollution is a stickier problem because nobody owns the climate or the air we breathe, and nobody CAN own them. Personally, I think we do actually need good government for some things, which is why I describe myself as "mostly libertarian".
And if I were King, I think I'd implement the Cato Institute's suggestion and give all of our National Parks and public wilderness to private environmental organizations to take care of (or sell, if they decided they could put the money to better use for something else).