Anglo-Norman Kings, having conquered Saxon England started collecting taxes methodically (The "Doomsday Book" is a famous example).
For accounting, they were using a large board with rows and columns not unlike a chessboard "un échiquier" in French (from Persian origin imported via Latin).
The responsible for this task was therefore named "Chancellor of the Exchequer". He had to verify that the numbers indeed matched expectations. From this exercise comes the verb "to check".
In the meantime, the European banking system, used "bills of exchanges" to credit and debit accounts between branches in various cities on behalf of their customers, Lombard were famous for this (Lombard Street in London) but they were far from being the only ones. This allowed for only paper to be transported which was both safer and easier.
From 1745 onwards, the bank of England had the exclusivity of money printing "au porteur" (payable to the bearer). This happened much later in the US, when the Federal Reserve was instituted. Private banker who could therefore not emit their own banknotes any more had to resort to a different type of bill that had to be "checked" because they were nominative.
The word "check" then went back to France, when they imported the concept, and they spelt it "cheque" and sometimes "checque" (I spared you the accents).
The word then went back again to England as "cheque" and only the US actually simplified it back to "check".
It should therefore be:
- "check" in the US
- "cheque" in the UK, AU, ZA and Canada
Update:
As for "checking" vs "chequing" vs "chequeing", my understanding is as follows:
- "Checking" accounts are used in the US,
- both "chequing" and "chequeing" are accepted in Canada with a marked predominance for the former although the latter is the correct original British English spelling.
- Actually, in the UK you don't hold "chequeing" accounts, but "cheque" accounts, but this phrase is seldom used; "current account" (as opposed to savings account") is preferred. However, when the gerund is used it is spelt "chequeing" (this is disputed however, see Brian's comments below).
- I'm told that in Australia, "cheque account" is used and "chequeing" is rare (comments below from staticsan).
Another famous "ping-pong"-type etymology between French and English is
"taster" (to grope for testing purposes) => "to taste" => "tester" (to try) =>
"to test"