c. 1300, gessen "to infer from observation, perceive, find out; form an opinion, judge, decide, discern; evaluate, estimate the number, importance, etc. of," perhaps from Scandinavian (compare Middle Danish gitse, getze "to guess," Old Norse geta "guess, get"), or from or influenced by Middle Dutch gessen, Middle Low German gissen "to guess," all from Proto-Germanic *getan "to get" (see get (v.)).
The prehistoric sense evolution then would be from "get," to "take aim at," to "to estimate." Meaning "to hit upon the right answer" is from 1540s. Spelling with gu- is late 16c., sometimes attributed to Caxton and his early experience as a printer in Bruges. Related: Guessed; guessing. Guessing game attested from 1650s. To keep (someone) guessing "keep him in a state of suspense" is from 1896, American English.
[T]he legitimate, English sense of this word is to conjecture; but with us, and especially in New England, it is constantly used in common conversation instead of to believe, to suppose, to think, to imagine, to fancy. [Bartlett, "Dictionary of Americanisms," 1848]