I have heard that it was something to do with Plague/Black Death where sneezing was an early symptom so one would say "God bless you" in the hope that God would ensure that it wasn't plague
Another version of medieval superstition is the belief that a devil may spring into your mouth as you opened it to sneeze - saying 'God Bless You' would prevent such an unfortunate event from occuring.
Re: Rekstout's answer - you might like to check the answer I gave for another question, which pours some doubt over this nevertheless widespread belief: question 9359
Whether it's true or not I'd heard that when you sneeze your heart pauses for a slight moment and the "bless you" is just a way of ensuring that it starts again.