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 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.
"to bungle, perform clumsily or badly," by 1840, said to be from pugilism slang, probably related to muff (n.) "awkward person, simpleton" (1837), which is perhaps from muff (n.) on notion of someone clumsy because his hands are in a muff. Related: Muffed; muffing. The noun meaning "anything done in clumsy or bungling fashion" is by 1871.