c.1400, "a dirty, slovenly, or untidy woman," according to OED "Of doubtful origin," but probably cognate with dialectal German Schlutt "slovenly woman," dialectal Swedish slata "idle woman, slut," and Dutch slodde "slut," slodder "a careless man," but the exact relationship of all these is obscure. Chaucer uses sluttish (late 14c.) in reference to the appearance of an untidy man. Also "a kitchen maid, a drudge" (mid-15c.; hard pieces in a bread loaf from imperfect kneading were called slut's pennies, 18c.).
Specific modern sense of "woman who enjoys sex in a degree considered shamefully excessive" is by 1966. Meaning "woman of loose character, bold hussy" is attested from mid-15c., but the primary association through 18c. was untidiness. Johnson has it (second definition) as "A word of slight contempt to a woman" but sexual activity does not seem to figure into his examples. Playful use of the word, without implication of messiness or loose morals, is attested by 1660s:
My wife called up the people to washing by four o'clock in the morning; and our little girl Susan is a most admirable slut, and pleases us mightily, doing more service than both the others, and deserves wages better. [Pepys, diary, Feb. 21, 1664]Cf. playful use of scamp, etc., for boys. Sometimes used 19c. as a euphemism for bitch to describe a female dog.