It's hard to say when it began, but it's a nearly worldwide tradition. Check out this page of different salutations: https://en.wikipedia.org/wiki/Response_to_sneezing
My belief is that it's generally because sneezing in a sign of illness, and illness tended to be more dangerous centuries ago, before antibiotics and when many people had less access to nutrition, consistent heating, sanitation and so forth.