The basic structure of a paradox of the preface is this. Take a number of claims, each of which has the following characteristic: we believe there is very good reason, of whatever relevant kind, to think that it is true. However, we still can have independent reason for thinking that almost certainly somewhere in this batch of claims there is some claim that is in fact false. So one way to gloss this is that we believe of each claim in the set that it is true but we believe of the set as a whole that it has at least one false claim. This is a paradox. The name comes from the usual scenario used to describe it, a scenario which was originally put forward by David Makinson (you can find Makinson's classic paper on his website). Suppose an author believes each sentence he writes in a book: he's very honest, and would never write a sentence he thinks is false. Moreover, he has taken great care in each case to make sure that he is right. So he has good reason to think that each one is true. But the author recognizes that he is fallible, and that with so many sentences in his book he certainly slipped somewhere. So in the preface to the book he admits that some sentences in the book are almost certainly false (perhaps hoping that someone might correct them if they find them). He has good reason to think each sentence is true, and good reason to think at least one of them is false.
Another, somewhat looser, way of putting the paradox is this. To assert contradictory things is irrational. The author believes what seem to be contradictory things. However, asserting what one thinks one has good reason to think true while at the same time recognizing one's own fallibility is rational. Makinson uses an analogy. A philosopher who says, "Every single one of my beliefs is currently correct," is exhibiting hubris, not rationality; but a philosopher who says, "It's pretty much guaranteed that some of my beliefs will turn out to be false," is being rational and honest. So either it's OK to believe contradictory things, or writing this preface seems both irrational and rational, or something weirder is going on. There are lots of different attempts to handle this; the most common of which is to deny that there is actually a contradiction by denying that beliefs (or good reasons, or certainty, or any of the other things you can run preface paradoxes with) agglomerate -- that is, that believing p is true and believing q is true doesn't logically require believing that both p and q are true. (For an example, see John Williams's discussion of the paradox (PDF).) This makes the logic governing the rationality of belief (or whatever) in a certain sense nonstandard; we can make sense of that, because there are perfectly viable logical systems that would allow this (certain kinds of modal logics), but there doesn't seem to be any general consensus about the best way to handle the preface paradox.
Pessin's argument is that religious belief has a structure similar to that which we find in the preface paradox:
[Y]ou can now say, first, that you believe, with certainty, on the basis of reason and evidence and testimony, in the truth of, say, the various individual tenets of your version of Christianity, and thus believe, with equal certainty, in all the things entailed by that belief: that, say, all other competing religions and doctrines are simply false.
But then you can say, second, something else: that you may be wrong.
Got it? You can simultaneously be certain that Christianity is true and everything conflicting with it is false, and yet acknowledge that you may be wrong without taking away your certainty. You can thus keep your certainties without having to claim that you are, in fact, and grossly implausibly, infallible.
He's surely right that the religious case can exhibit the preface paradox structure. I'm not sure it's quite such a revelation as he thinks, because one would expect preface paradoxes to arise, at least potentially, wherever we can consider beliefs both individually and as a group. Indeed, as Makinson noted in his original article, the paradox of the preface is a cousin to MacIver's paradox (e.g., "I'm fairly sure that such-and-such is the case, but I know I could be wrong"); and MacIver's paradox crops up everywhere in discussing rationality. Pessin is implicitly taking a positon on how to handle the preface paradox here, but it's not an unusual one. He's saying that, despite the apparent contradiction in the paradox, there is no actual contradiction; this is how almost everyone handles preface paradoxes. And Pessin is certainly right that insofar as the religious case exhibits the preface paradox structure, someone could reasonably be fully certain of each thing said by (say) Islam that it is true without necessarily being fully certain that there is nothing in Islam that is false. Thus, says Pessin, you can be a Humble Absolutist.
There's nothing out of the pale here; the preface paradox is an actual epistemological paradox, it is unsurprising that it or an analogous paradox can obtain in the religious case, and the solution that Pessin is assuming is a fairly common one that was formulated for purely epistemological reasons and can be given a solid logical grounding. And since Pessin is simply aiming at the "Humble Absolutist" claim, the preface paradox structure is actually the outside limit -- it's stronger than he actually needs for the conclusion he draws, but since one can draw similar conclusions for the preface paradox, one can, a fortiori, draw those conclusions in the weaker case. I'm not sure why Pessin is so excited about it; but, then, I haven't seen anyone apply it directly to the religious case before, so it was certainly worth doing.
In any case, here we enter Coyne's hilariously funny post, which makes me burst into laughter every time I read it. His summary of Pessin's argument?
How can you be dead certain that the tenets of your faith are right and still tell others that the contradictory tenets of their faiths might also be right?
Pessin’s solution: you just assert it.
This in a post titled, "Religious beliefs can be true and false at the same time." This is such a mockably bad misreading of the paradox that I still can't get over it; it's not as if we're dealing with an especially difficult point to grasp here, nor as if it takes much epistemological or logical acumen to see the point, nor does it exactly take a genius to figure out the basic structure of Pessin's argument. And it's all the funnier in the logical equivocation that Coyne's question carries, which shows that he has missed the whole point and then some: Pessin is saying you can be "dead certain" of each tenet that it is right, but still recognize, on the basis of one's fallibility, that some of those tenets (you don't know which ones) might actually be false. That is, there are two different ways of being "dead certain" about the tenets of one's faith; and there are, correspondingly, two different ways to concede that exclusive tenets might be true. But Coyne, of course, doesn't see the need to bother with trifles like logic and rational approaches to epistemology.
It wouldn't be so bad if he didn't try to smear Andrew in the process of displaying his ignorance and logical incompetence; but his doing so simply takes the cake. But we can't be too hard on him; he's Coyne -- consideration of the possibility of his own fallibility, and what might follow from it logically and epistemologically, is just plain foreign to him, so we should have some sympathy for his difficulty in grasping the elementary issues of it.
(Incidentally, my own preferred approach to resolve preface paradoxes generally is fairly similar to Dale Jacquette's (PDF), who also has a good discussion of different kinds of proposals.)
ADDED LATER: Jean Kazez provides a sharp contrast with Coyne by having a reasonable discussion of Pessin's argument.
What has actually surprised me in some of the discussion throughout the blogosphere is that there are people in the discussion with backgrounds in philosophy who seem to have no real acquaintance with the paradox. For instance, there seems a common misconception that the paradox can be dissolved simply by eliminating the issue of certainty; but this is provably untrue (and has been known for decades now), and most versions of the preface paradox that have been developed since Makinson's first identification of it do not appeal to certainty. You can run preface paradoxes for almost any concept associated with rationality, including several that do not require certainty. It is, as I note above, possible to have a preface paradox in virtually any conditions under which you can treat beliefs, claims, assertions, etc., both individually and as a group. Precisely the reason philosophers have studied it is that it cannot be easily waved away.