1620s, "piece of wood or other substance, usually in the form of a peg or bottle-cork, used to stop a hole in a vessel," originally a seamen's term, probably from Dutch plug, Middle Dutch plugge "bung, stopper," related to Norwegian plugg, Danish pløg (the Scandinavian words also might be from Low German), North Frisian plaak, Middle Low German pluck, German Pflock; all of uncertain etymology. The Irish and Gaelic words are said to be from English.
The sense of "wad or stick of tobacco" is attested from 1728, based on resemblance. Meaning "branch pipe from a water main leading to a point closed by a cap where a hose can be easily attached" is by 1727. Electrical sense is from 1883, based on being inserted; meaning "sparking device in an internal combustion engine" is from 1886. Meaning "advertisement" is recorded by 1902, American English, perhaps from verb sense "work energetically at" (c. 1865).
"close tightly (a hole), fill or stop with or as with a plug," 1620s, from plug (n.) or from Dutch pluggen. OED dates the meaning "work energetically at" from c. 1865, and cites "Remembered on the river at Oxford" (and one wonders if a memory from Cambridge would pass). Sense of "popularize by repetition" is from 1906. Slang sense "put a bullet into" is recorded from 1870. Related: Plugged; plugging.