Old English ceorl "peasant, one of the lowest class of freemen, man without rank," from Proto-Germanic *kerlaz, *karlaz (source also of Old Frisian zerl "man, fellow," Middle Low German kerle, Dutch kerel "freeman of low degree," German Kerl "man, husband," Old Norse karl "old man, man").
It had various meaning in early Middle English, including "man of the common people," "a country man," "husbandman," "free peasant;" by 1300, it meant "bondman, villain," also "fellow of low birth or rude manners."
For words for "common man" that acquire an insulting flavor over time, compare boor, villain. In this case, however, the same word also has come to mean "king" in many languages (such as Lithuanian karalius, Czech kral, Polish król) via Charlemagne.