From one of those q and a columns in the Arizona Republic about sneezing comes the passing comment:

As to the bless-you part, nobody seems to know where that came from either.

It's been going on forever. Pliny mentioned it in his Natural History in A.D. 77.

Poking around the net finds something at Sacred Texts which says:

But the true story of the sneezing superstition is told by Professor E. B. Tylor, who says:--

"In Asia and Europe the sneezing superstition extends through a wide range of race, age, and country. Among the passages relating to it in the classic ages of Greece and Rome, the following are some of the most characteristic: the lucky sneeze of Telemachus in the Odyssey; the soldier's sneeze and the shout of adoration to the god which rose along the ranks, and which Xenophon appealed to us a favourable omen; Aristotle's remark that people consider a sneeze as divine, but not a cough; the Greek epigram on the man with the long nose who did not say Zeu Soson when he sneezed, for the noise was too far off for him to hear; Petronius Arbiter's mention of the custom of saying 'Salve' to one who sneezed; and Pliny's question 'Cur sternutamentis salutamus?' a-propos of which he remarks that even Tiberius Caesar, that saddest of men, exacted this observance.

A quick search of Pliny for this 'question' points to NH 28.23 ... there's also an interesting whack of ancient refs in Thomas Browne's Pseudodoxia Epidemica ...