1590s, "covering into which both hands may be thrust to keep them warm," from Dutch mof "a muff," shortened from Middle Dutch moffel "mitten, muff," from Middle French moufle "mitten," from Old French mofle "thick glove, large mitten, handcuffs" (9c.), from Medieval Latin muffula "a muff," a word of unknown origin.
The muff was introduced into France toward the close of the sixteenth century, and soon after into England. It was used by both men and women, and in the seventeenth century was often an essential part of the dress of a man of fashion; but it is now exclusively an article of female apparel. [Century Dictionary]
Meaning "vulva and pubic hair" is from 1690s; muff-diver "one who performs cunnilingus" is from 1935.