The origin of pumpernickel is relatively clear — the first part, at least, derives from the onomatopoeic German word Pumpf, or fart (Anatoly Lieberman has an interesting column connecting to pimp, and pimp to the history of faggot).
But there is a folk etymology that tells this story: when Napoleon was marching through Westphalia, he was given some of their rough, dark bread, and he said it was only “bon pour Nicole” — good for Nicole, his horse. Steven Pinker, in his book The Language Instinct, credits this to an unnamed journalist, who later confessed to making the story up. The story is told on page 397 of the book, but its origin is not cited, although Pinker is usually pretty thorough with his sources.
I did some research today, trying to track down the origin — I think I’ve discovered that the folk etymology predates Napoleon, and comes from the 17th century. I found the following quote in a 1908 Jahrbuch des Vereins für Niederdeutsche Sprachforschung (thanks, Google Books!):
Da is zuerst die witzige Auslegung von Schuppius: “Bon pour Nicol”, gut für den Nickel, worunter ein kleines schlechtes Pferd verstand werden soll; Pumpernickel wäre also gutes Pferdefutter.
There is first the witty interpretation of Schuppius: “Bon pour Nicol”, good for Nickel, by which a small, weak horse should be understood; pumpernickel would make good horse fodder.
Schuppius is Johann Balthasar Schupp, the 17th century satirist and poet, thus predating Napoleon. In his book, Der rachgierige und unversöhnliche Lucidor erinnert und ermahnt (The vengeful and unforgiving Lucidor reminds and warns, approximately 1655), Schupp writes:
Ein Westfälischer Bauer aber würde kaum dafür danken sondern lieber ein stück Speck und Bon pour Nicol habelnwollen.
A Westphalian farmer wouldn’t give thanks for that; but would rather have a piece of bacon and ‘bon pour Nicol.’
Here is a scan (from Google Books) of this passage: