The various phrases containing the word mustard are based on the image of something which adds heat or pungency (the same underlying metaphor is present in hot stuff and in some acceptations of hot mess).

Originally American English, to cut the mustard and to be (all to) the mustard (also to be the proper mustard) are first recorded, respectively, in the late 19^th and early 20^th centuries. In these phrases, mustard refers to something or someone excellent, which or who sets the standard.

Most often used in the negative form, to cut the mustard means to come up to expectations, to meet requirements, to succeed. (Here, cut means to outdo, so that the phrase conveys the image of surpassing something or someone already excellent.)

The earliest instance of to cut the mustard that I have found is from the Lexington Weekly Intelligencer (Lexington, Missouri) of 13^th March 1886:

Sam went to see Miss Mollie last Sunday evening, and as the butter and biscuit had given out, Sam did not stay long. Sam you could not cut the mustard.

The second-earliest occurrence that I have found is from The Clinton Eye (Clinton, Missouri) of 27^th March 1886:

There is one grand reason why Thomas J. Lingle will not attend to the post-office duties at Clinton: he “didn’t cut the mustard.” But when he got home he published such a fine article on the bosses, and we read it, and so did one or two others.

The phrase to be (all to) the mustard means to be exactly what is required, to be very good or special. The earliest instance that I have found is from the Daily News (Mount Carmel, Pennsylvania) of 11^th February 1903:

The production of “A Millionaire Tramp” at the G. A. R. opera house last evening by the Elmer Walters Company was good […].
The general opinion of the people who witnessed the performance was that the play was “all to the mustard.” The gallery gods yelled “Come again,” and yelled it more than once, too, when the curtain dropped on the last act.

The phrase to be the proper mustard is first recorded in The Log of a Cowboy: A Narrative of the Old Trail Days (Boston and New York, 1903), by Andy Adams (1859-1935), American novelist and short-story writer:

A man […] gave a thousand dollars for a pair of dogs before they were born. The terms were one half cash and the balance when they were old enough to ship to him. And for fear they were not the proper mustard, he had that dog man sue him in court for the balance, so as to make him prove the pedigree.

A later phrase, apparently of British-English origin, to be mustard, means, of a person, to be regarded as very sharp, keen, or accomplished, in a particular sphere. An early instance is from the Gloucester Journal (Gloucester, Gloucestershire) of 1^st May 1915, which published a letter that a British soldier had written about his experience on the Western Front:

Our fellows are “mustard” in locating German snipers, and are laying claim to have silenced one or two.

Two other phrases, referring to the heat or pungency of mustard, had appeared much earlier, in the second half of the 17^th century: as strong, or as hot, as mustard, and as keen as mustard.

The phrase as strong, or as hot, as mustard, meaning very powerful or passionate, is first recorded in Παροιμιογραϕια [= Paroimiographia] Proverbs, or, Old sayed sawes & adages in English (or the Saxon toung), Italian, French and Spanish (London, 1659), by James Howell (circa 1594-1666), historian and political writer:

As weak as Water.
As strong as Mustard.
As bitter as Gall.

The phrase as keen as mustard, meaning very enthusiastic, is attested in Phraseologia Anglo-Latina or, Phrases of the English and Latin tongue Together with Parœmiologia Anglo-Latina or, A Collection of English and Latin proverbs (London, 1672), by William Walker (1623-84), schoolmaster and author; in the chapter titled Adagia Petroniana, as keen as mustard translates Latin piper, non homo.

The expression piper, non homo, literally pepper, not a man, is from The Satyricon, by Gaius Petronius (died AD 66):

Sed memini Safinium; tunc habitabat ad arcum veterem, me puero: piper, non homo.
     (translation: Michael Heseltine, 1913)
I remember Safinius: he used to live then by the old arch when I was a boy. He was more of a mustard-pot than a man.