Old English stice "a prick, puncture, sting, stab," from Proto-Germanic *stikiz (source also of Old Frisian steke, Old High German stih, German Stich "a pricking, prick, sting, stab"), from PIE *stig-i-, from root *steig- "to stick; pointed" (see stick (v.)). The sense of "sudden, stabbing pain in the side" was in late Old English.
Senses in sewing and shoemaking first recorded late 13c.; meaning "bit of clothing one is (or isn't) wearing" is from c. 1500. Meaning "a stroke of work" (of any kind) is attested from 1580s. Surgical sense first recorded 1520s. Sense of "amusing person or thing" is 1968, from notion of laughing so much one gets stitches of pain (compare verbal expression to have (someone) in stitches, 1935).