mid-14c., from O.Fr. eschec mat, from Arabic shah mat "the king died" (see check (n.)), which according to Barnhart is a misinterpretation of Persian mat "be astonished" as mata "to die," mat "he is dead." Hence Persian shah mat, the ultimate source of the word, would be literally "the king is left helpless, the king is stumped." As a verb, from late 14c.
Here is a nicer description from word-orgins.com
Checkmate (14th c.) comes via Old French eschec mat from Persian shāh māt ‘the king is left helpless’ ... From the very specific chess sense there developed more general applications such as ‘attack’, ‘arrest’, ‘stop’, ‘restrict’, and ‘verify’. Among these in the 18th century was ‘token used as a counterfoil for verifying something, such as an amount’. As check this survives mainly in American English (as in ‘hat-check’)
Check as in ‘pattern of squares’ (14th c.) is probably short for chequer, which in turn is a reduced form of exchequer, a word derived ultimately from Vulgar Latin *scaccus.