Why cutting mustard was chosen as an example of high quality is unclear. As always in such circumstances, there are no shortage of guesses. Some of these allude to the literal difficulty of cutting mustard in its various forms; for example:
- Mustard seed, which is hard to cut with a knife on account of its being small and shiny.
- Mustard plants, which are tough and stringy and grow densely.
- Culinary mustard, which is cut (diluted) and made more palatable by the addition of vinegar.
There is no evidence to support these derivations and they give the impression of having been retro-fitted in an attempt at plausibility.
Another supposed explanation is that the phrase is simply a mistaken version of the military expression 'cut the muster'. This appears believable at first sight. A little research shows it not to be so. Muster is the calling together of soldiers, sailors, prisoners, to parade for inspection or exercise. To cut muster would be a breach of discipline; hardly a phrase that would have been adopted with the meaning of success or excellence. This line of thought appears to have been influenced by confusion with the term 'pass muster', which would have the correct meaning, but which could hardly be argued to be the origin of 'cut the mustard'. The OED, which is the most complete record of the English language, along with all of the other reference works I've checked, don't record 'cut the muster' at all. The fact that documented examples of 'cut the mustard' are known from many years before any for 'cut the muster' would appear to rule out the latter as the origin.
There has been an association between the heat and piquancy of mustard and the zest and energy of people's behaviour. This dates back to at least 1672, when the term 'as keen as mustard' is first recorded. 'Up to mustard' or just 'mustard' means up to standard in the same way as 'up to snuff'. 'Cutting' has also long been used to mean 'exhibiting', as in the phrase 'cutting a fine figure'. Unless some actual evidence is found for the other proposed explanations, the derivation of 'cutting the mustard' as an alternative way of saying 'exhibiting one's high standards' is by far the most likely.
Whatever the coinage, the phrase itself emerged in the USA towards the end of the 19th century. The earliest example in print that I've found is from The Iowa State Reporter, August 1897, in a piece about the rivalry between two Iowa towns:
Dubuque had the crowds, but Waterloo "Cut the Mustard"
The use of quotation marks and the lack of any explanation of the term in that citation imply that 'cut the mustard' was already known to Iowa readers and earlier printed examples may yet turn up.