The alt.english.usage FAQ states that the story originated with an anecdote in Sir Ernest Gowers’ Plain Words (1948). Supposedly an editor had clumsily rearranged one of Churchill’s sentences to avoid ending it in a preposition, and the Prime Minister, very proud of his style, scribbled this note in reply: “This is the sort of English up with which I will not put.” The American Heritage Book of English Usage agrees.
The FAQ goes on to say that the Oxford Companion to the English Language (no edition cited) states that the original was “This is the sort of bloody nonsense up with which I will not put.” To me this sounds more likely, and eagerness to avoid the offensive word “bloody” would help to explain the proliferation of variations.
A quick search of the Internet turned up an astonishing number. In this era of copy-and-paste it’s truly unusual to find such rich variety. The narrative context varies too: sometimes the person rebuked by Churchill is a correspondent, a speech editor, a bureaucrat, or an audience member at a speech and sometimes it is a man, sometimes a woman, and sometimes even a young student. Sometimes Churchill writes a note, sometimes he scribbles the note on the corrected manuscript, and often he is said to have spoken the rebuke aloud. The text concerned was variously a book manuscript, a speech, an article, or a government document.
Here is just a sample of the variations circulating on the Net:
Then there are those who get it so scrambled it comes out backward:
Ben Zimmer has presented evidence on the alt.usage.english list that this story was not originally attributed to Churchill at all, but to an anonymous official in an article in The Strand magazine. Since Churchill often contributed to The Strand, Zimmer argues, it would certainly have identified him if he had been the official in question. It is not clear how the anecdote came to be attributed to Churchill by Gowers, but it seems to have circulated independently earlier.