If you want to stop your neighbor from smoking...

You don't like cigar and your neighbor smokes a lot. What will you do? Kill him? Oh, it's a 'mafia' or 'yakuza' solution. Economics may have milder solution to it! Ask him, "would you mind if I asked you not to smoke??" If he says 'Yes, I would!', then you will ask him to offer a trade like this: how much should I pay if you stop smoking for me?? The smoke is 'the negative externality' that makes you feel bad, while the nonsmoke the negative externality that irritates your neighbor. So there's some room for you to make such a deal if you want to solve the problem.    

According to Mankiw's best-seller introductory textbook, "the Coase Theorem is the proposition that if private parties can bargain without cost over the allocation of resources, they can solve the problem of externalities on their own." (2007,POE, 4th. ed., pp210-211)

The Coase Theorem says that the efficient (Pareto-efficient) amount of the good involved in the externalities is independent of the distribution of property right if there is no income effect, which means that the efficient allocation will be achieved if the demand for the good causing the externality doesn't depend on the distribution of income.
(Varian, Hal,2003,Intermediate micro, 6th ed., pp607-608)

But I recall the debate on the transaction cost:

(1) The Coase theorem implies that if the transaction cost is zero(or if the interest parties have no trouble reaching and enforcing an agreement), it doesn't matter who we assign property rights to.

(2) The Coase theorem implies that if the transaction costs are less than the gains from trade (or if the interest parties may have some trouble reaching and enforcing an agreement, but they agree that the gain from the trade will be greater than the time and money it costs and takes to reach an agreement ), it doesn't matter who we assign property rights to.

Which is right? I think these above 2 statements are (almost) equivalent, but (1) is stronger statement than (2).
Though Mankiw's text takes the former and some economists the latter, Mankiw's text says that if the benefit of solving the externality problem is less than the transaction cost of reaching the beneficial trade, the problem will leave unsolved or it matters who we give the property rights to and the Coase Theorem doesn't apply.

Thus even if there's some positive transaction cost,  the Coase Theorem will apply as long as the benefit of the trade is greater than the cost of agreeing the trade.