Either to stick to or to part from. A man “shall cleave to his wife” (Matt. xix. 5). As one that “cleaveth wood” (Psalm cxli. 7). The former is the Anglo-Saxon clíf-an, to stick to, and the latter is cleof-an, to split.
Source: Dictionary of Phrase and Fable, E. Cobham Brewer, 1894
More on Cleave from Infoplease: