[pulplobster]

My guess is that they use a probabilistic model that, for every tap, incorporates the probability distributions P('a'| X), ..., P('z' | X), X=(x,y) probably a normal distribution. Then assuming they have data on how likely a specific word is, you'd estimate the posterior probability distribution over all the possible words with that many characters. Pick the top most probable words as auto correct options.

I'm sure there's more to it than that, but I assume that's the basic idea.