1660s, "to denote secondarily," from Medieval Latin connotare "to signify in addition to the main meaning," a term in logic, literally "to mark along with," from assimilated form of Latin com "with, together" (see con-) + notare "to mark, note, make a note," from nota "mark, sign, means of recognition" (see note (n.)). Meaning "to signify, constitute the meaning of a word" is from 1829 (J.S. Mill); hence, in extended general sense "to imply" (1865). Related: Connoted; connoting.
A word denotes its primary meaning, its barest adequate definition -- father denotes "one that has begotten." A word connotes the attributes commonly associated with it -- father connotes "male sex, prior existence, greater experience, affection, guidance."