Its proponents often trace it to the American Civil War.
We do have the analogous expression “to pass muster," which probably first suggested this alternative; but although the origins of “cut the mustard" are somewhat obscure, the latter is definitely the form used in all sorts of writing throughout the twentieth century.
Common sense would suggest that a person cutting a muster is not someone being selected as fit, but someone eliminating the unfit.
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 than butter.
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".