Neyther mayst thou ryse, cough, spyt, or nese

A. Barclay, Egloges, ca. 1530

The word 'sneeze' was originally 'fneeze' and is related to Old Norse fnaesa = snort or sneeze. But it lost its initial 'f', and became  'nese', probably because 'fn' is such a rare word beginning in English (I can't find any examples in modern English). But later it acquired an 's'. Perhaps people thought the 'f' was a long s, ƒneeze, or possibly as the Oxford English Dictionary suggests adding an initial 's' to 'nese' made it sound sneezier. The word 'cough' sounds like a cough (it's echoic) and 'sneeze' sounds like a sneeze.

Going further back, 'fneeze, is probably from the same older root as Greek πνευ (pneu) = breath, as in pneumonia. 

This change from p to f, going from Greek/Latin to Germanic languages, is a regular feature, first articulated by Schlegel in 1806. Other examples are pyr->fire, pod->foot, pater->father, penta->five, pulo->fowl, and (more surprisingly) port -> ford. (So a ford is a gateway/door (or port)). 

See here for more discussion about this sound change, part of Grimm's (one of the fairy tale brothers) law.