Nigel Rees, A Word in Your Shell-like (2004) suggests that the phrase “put up or shut up” may mean different things in the United States and in the UK:
put up or shut up! 'Either make good your argument or stop talking about it'. In America, this translates as 'put up your money (as though for a bet)' but in Britain, 'put up your fists (as though for a fight)'. Both uses probably dating from the 19th century.
The entry for "put up or shut up" in Harold Wentworth & Stuart Flexner, Dictionary of American Slang (1960) identifies a specific instance of the phrase from 1894:
put up or shut up 1 Lit., back up your opinion with a money wager or be silent about it. 2 Fig., prove your assertion by some definite action or stop making the assertion. 1894: Thornton. Colloq. Used orig. as an invitation to wager, but now more in anger as a command to shut up.
But the phrase appears earlier still in Mark Twain, A Connecticut Yankee in King Arthur's Court (1889):
I was not bluffing this time. I meant what I said ; I could do what I promised. There wasn't any way to misunderstand the language of that challenge. Even the dullest of the chivalry perceived that this was a plain case of "put up, or shut up." They were wise and did the latter.
An even earlier occurrence is in an 1877 translation of Meilhac & Halevy, The Widow: A Comedy in Three Acts (1877):
GAETAN. Oh, you wouldn't rob a friend out of his hard earnings, would you?
GEORGES. Wouldn't I? Show your hand, or forfeit your money. In coarse parlance, "put up or shut up."
And earlier still, from George Barclay, The Life and Remarkable Career of Adah Isaacs Menken, the Celebrated Actress (1868), we have this:
As one of the parties of this "ill assorted union" still survives, it would, perhaps, be wise for me to refrain from any remarks to the why, and wherefore, and furthermore, said surviving party being "on the muscle," and much " bigger than I," he might challenge me to "put up or shut up." Now at the present time I can neither put up my mauleys" in a "twenty-four foot ring" with the requisite amount of money, nor can I find any persons to back me, as regards the "filthy lucre." There is one thing I can do—shut up. "Mum's the word."
This last instance suggests that the phrase may have arisen in the demimonde of pugilism, and that it may have meant both accepting a challenge to fight and betting money on the outcome of that fight.
Oddly, J. S. Farmer & W. E. Henley, Slang and Its Analogues (1902), which doesn't have an entry for "put up or shut up," states that the imperative "put up!" means, essentially, "shut up!":
PUT UP! = Shut your mouth! (American)
—which, if substituted into the phrase "Put up or shut up," would make its meaning "shut your mouth or shut up." It seems highly likely, though, that "put up!" in the sense of "shut your mouth" and the phrase "put up or shut up" either arose independently of one another or with "put up!" emerging as a truncated form of the longer expression.
UPDATE (December 7, 2016): Instances of 'put up or shut up', 1863–1865
Between the July 21, 1858, item cited in Hugo's answer and the July 10, 1865, item cited there, Elephind reports five additional independent instances of the expression—four from the New York Clipper (which also published an item on the original 1858 challenge by John Morrissey ten months later, on April 16, 1859), and one from the Montana Post. Here is a quick look at those instances.
From "The Wrestling Championship: Harry Hill to Mr. Ainesworth" in the New York Clipper (March 28, 1863):
We have received the following card from Mr. Hill, in reference to a match talked about between himself and Ainesworth. Some few days since, a bet of $20 was made that these men wouldn't make a match for $1,000 a side within thirty days, and this is what Harry Hill has to say about it:
EDITOR CLIPPER—The friends of Mr. Ainesworth, having literally defied me to a wrestling encounter with the American Champion, I hereby publicly notify them that I accept the challenge, and will wrestle the collar and elbow hold, first fall, for the sum of $500. I would designate four weeks hence as the time, and New York as the locality, and, if demurred to, will toss for the settlement. It was never my purpose to enter as a professional, but, being bade "to put up or shut up," I have felt disposed to evade the public requirement. HARRY HILL
From "Wrestling Match: For the Championship and One Thousand Dollars, Harry Hill the Victor" in the New York Clipper (April 25, 1863):
We have had many enquiries addressed us, desiring our opinion whether this match was really "on the square" or not, and if the men actually wrestled for the amount staked, viz.: $1,000. In reply, we do not feel justified in expressing any opinion whatever on either point, but merely append the following card from Ainsworth, leaving our readers to draw their own conclusions. Hill declines wrestling any more:—
NEW YORK, April 15, 1863. I will wrestle any man in the world, not exceeding my weight (145 pounds) more than thirty pounds, for any sum of money intervening between one and ten thousand dollars, collar and elbow hold, best two in three, anywhere and at any time; money now ready to be deposited. The forfeiture to be made to be sufficiently large to insure business. If this challenge is accepted abroad, my travelling expenses to be paid to the particular locality designated, unless the applicant prefers the United States, in which event I will pay his traveling expenses. Now to all the world I say either "put up or shut up." L. AINSWORTH
From "The Ring" in the New York Clipper (August 22, 1863):
ED. CLIPPER.—Sir:—I perceive there's another challenge from Farley in your lost week's journal, making the third time he has thus brought his name before the public for notoriety's sake. A year ago I offered to give him five pounds in weight to fight me and he declined. In about five months he had only four challenges in the CLIPPER for me, and I gave him his choice, resulting in a match to fight on the fifth of July for $250 a side. For this I threw up my business, and after training three weeks Farley forfeited $75. In that three weeks my expenses were $200, besides neglecting my saloon and pupils, equal to $150 each. When I went for the forfeit, this man Farley and some of his crowd threatened to mob me for taking the money. I asked him if I hadn't used him like a gentleman , and his answer was that "he had never asked me to;" this from an individual who wants to be considered a sporting man. Here's what I will do, and nothing else: I will fight Farley for $500 a side , or as much more as he likes, at 125lbs. It won't pay me to fight for less. If that suits Mr. F., let him put up or shut up. Any other satisfaction he wants can be had without newspaper talk, as I am always to be found at 79 Front street, and he knows it. JOHNNY HEALEY, alias "Bob."
From "A Challenge," in the [Virginia City] Montana Post (November 5, 1864):
Having heard that Tom. Foster is dissatisfied with the reslt of his fight with me, and thinks he would have a better show in Bannack, I do hereby challenge him to fight me a fair stand up fight, anywhere within one hundred miles of this city, for any amount he may see fit, but not less than one thousand dollars, in any reasonable length of time. A deposie sent to this office will be covered at once, without further parley. Put up or shut up. JOSEPH RILEY.
From "The Ring" in the New York Clipper (May 27, 1865):
JOHNNY HICKEY'S RESPONSE TO GRIFFIN, OF ALBANY.—In response to Griffin, of Albany, Johnny Hickey says that he will meet Griffin in the fistic arena for $l,000 or more a side, at 115 lbs., give or take a pound, in three months after signing articles. Hickey has left $50 with us as an earnest of his intentions, so that he has put Griffin in position to "put up or shut up," as the above is substantially according to his (Griffin's) own proposition. Conclusive arrangements can be made at Mike Trainor's Hotel, in Chatham steeet, New York, or by sending signed articles to the CLIPPER office, accompanied by the necessary $50 or more as forfeit If Griffin fails to respond in the affirmative, Hickey win fight any other man in Uncle Sam's dominions on the same terms. Thus sayeth Johnny.
All of these instances corroborate the conclusion that Hugo's answer reached: "put up or shut up" probably arose in the context of prize fights as a succinct (and soon formulaic) way of saying "I'm willing to bet X amount of money that I will win a fight between us. Match that amount with an equal sum of your own and meet me in the ring, or stop talking about how much you want to fight me."