"lowest and principal timber of a ship or boat," mid-14c., probably from a Scandinavian source (compare Old Norse kjölr "keel," Danish kjøl, Swedish köl), which according to Watkins is from Proto-Germanic *gwele- (3) "to swallow" (see gullet).
OED and Middle English Compendium say this word is separate from the keel that means "a strong, clumsy boat, barge" (c. 1200), which might be instead from Middle Dutch kiel "ship" (cognate with Old English ceol "ship's prow," Old High German kiel, German Kiel "ship"). But the two words have influenced each other or partly merged, and Barnhart calls them cognates. Keel still is used locally for "flat-bottomed boat" in the U.S. and England, especially on the Tyne.
In historical writing about the Anglo-Saxons, it is attested from 17c. as the word for an early form of long-boat supposedly used by them in the crossing, based on ceolum in the Anglo-Saxon Chronicle and Medieval Latin cyulis (Gildas). Old English also used simply scipes botm or bytme. On an even keel (1560s) is "in a level, horizontal position," hence figurative extension with reference to stability.