Arnold Zwicky of Language Log has reported on a long-needed investigation into the history of the cliché (or, to a Language Logger, “snowclone”) What is this X of which you speak? I’m astonished to learn it was already being bandied about in Usenet in 1983:
There has been a lot of net discussion about “toilet paper” recently. Just what is this “toilet paper” of which you speak? Where can I find it? (from net.misc, 24 August 1983 (link))
But there doesn’t seem to be an actual, identifiable original from which the parodies were derived: “The origin seems to be in the collective memory of big-screen and small-screen science fiction from the ’50s and ’60s.” There is also discussion of the spurious quotation “Kiss”? What is “kiss”?. Now if only the Loggers would get to work on alternative negations.
Update (August 2015). Commenter charlieO has found a superb antedate from Matthew Lewis’s The Monk (1796): “Father, you amaze me! What is this love of which you speak?” The novel was wildly popular in its day, and it seems reasonable to assume that parodies of Gothic novels (such parodies were also wildly popular) regularly featured this template, which survived to make it into Douglas Adams and a new generation of snarky youth. I note that according to Wikipedia the novel was “written in ten weeks, before [Lewis] turned 20”; he probably would have enjoyed Douglas Adams himself.