early 15c., smogen "to soil, stain, blacken," of obscure origin. Meaning "to rub out or in" is by 1865. Related: Smudged; smudging. The noun meaning "a dirty mark or stain, spot, smear" is attested by 1768, from the verb.
The smudge meaning "make a smoky fire" is by 1860, also of unknown origin, but perhaps related. According to OED now dialectal and North American. OED also gives it in an earlier, obsolete sense of "to cure (herring) by smoking" (1590s).
The related noun smudge is attested by 1767 as "a suffocating smoke" (to repel mosquitoes, etc.); from 1806 as "heap of combustibles ignited and emitting dense smoke." Hence smudge-pot (1903). Smudge-stick as a Native American (Crow tribe) artifact is by 1908