This article is from the alt.usage.english FAQ, by Mark Israel firstname.lastname@example.org with numerous contributions by others.
This expression meaning "to achieve the required standard" is
first recorded in an O. Henry story of 1902: "So I looked around
and found a proposition [a woman] that exactly cut the mustard."
It may come from a cowboy expression, "the proper mustard",
meaning "the genuine thing", and a resulting use of "mustard" to
denote the best of anything. O. Henry in "Cabbages and Kings"
(1894) called mustard "the main attraction": "I'm not headlined
in the bills, but I'm the mustard in the salad dressing, just the
same." Figurative use of "mustard" as a positive superlative dates
from 1659 in the phrase "keen as mustard", and use of "cut" to
denote rank (as in "a cut above") dates from the 18th century.
Other theories are that it is a corruption of the military phrase
"to pass muster" ("muster", from Latin "monstrare"="to show", means
"to assemble (troops), as for inspection"); that it refers to the
practice of adding vinegar to ground-up mustard seed to "cut" the
bitter taste; that it literally means "cut mustard" as an example of
a difficult task, mustard being a relatively tough crop that grows
close to the ground; and that it literally means "cut mustard" as
an example of an easy task (via the negative expression "can't
even cut the mustard"), mustard being easier to cut at the table
The more-or-less synonymous expression "cut it" (as in "'Sorry'
doesn't cut it") seems to be more recent and may derive from
"cut the mustard".