The earliest Google Books search result I could find for "put [someone] up" in the sense of "provide temporary sleeping accommodations for [someone]" is from 1903, but other idiomatic meanings of "put [someone or something] up" go back at least to 1640. I'll address the usage specifically cited in the OP's question first, and then look at some of the earlier meanings of the phrase.
The earliest Google Search match is from Henry James, The Ambassadors (1903):
Chad offered him, as always, a welcome in which the cordial and the formal—so far as the formal was the respectful— handsomely met; and after he had expressed a hope that he would let him put him up for the night Strether was in full possession of the key, as it might have been called, to what had lately happened. If he had just thought of himself as old Chad was at sight of him thinking of him as older : he wanted to put him up for the night just because he was ancient and weary.
From Margaret Good, "Search for Fresh Buttermilk and Happiness by an Unmarried Woman," in Farm Journal (March 1909):
When father got her [a cow] out, he pulling at her head and we two women pushing with all our might, he seemed in the greatest perplexity as to where to put her up for the night. For a while he insisted that we take her up and put her in the west corner bedroom. But I bravely led the way to the stable, and the trembling little thing was in her corner before she knew it.
From The Michigan Alumnus, volume 28 (January 19, 1922):
The next meeting will take place on the last Friday in January at the home of Helen Blair Irwin, 3227 Carter Ave. Will out-of-town '16ers please try to join us that evening for a 6:30 supper? We will be glad to put you up for the night. Make a struggle and come.
I suspect that this idiomatic usage arose out of the earlier usage of to "put up" in the sense of "set up, establish, pack, store, or provide," as exemplified by testimony from Isaiah Look, in Investigation into the Charges of Mismanagement and Cruelty at the Soldiers' and Sailors' Home, Bath, New York" (1883):
Q. What request did he [the quartermaster] make for you to put vegetables for him going downtown?
A. He requested me to put up vegetables, having permission from the General to give them to his friends.
Q. What did you do?
A. I put them up according to orders.
A. On the farm.
Q. What vegetables did you put up?
A. That would be rather a hard question, green corn, green peas, apples, carrots, parsnips, radishes, cabbages, etc.
Q. You say you put them up for him; where in the wagon?
A. I never put any in the wagon but twice; I have taken them to his house myself, and sent them there.
The notion of temporary storage (in this case of vegetables in a wagon) prefigures temporary accommodation of people in a dwelling.
The two earliest meanings of "put [pronoun] up" that a Google Books search finds are the senses "nominate or present [a person for political office]" and "store or make ready [a thing for future use]." The "put [a person] up for office" sense appears first in "The Trial Between Sir William Pritchard and Thomas Papillon Esq" (November 6, 1684), in A Complete Collection of State-Trials and Proceedings for High Treason, and Other Crimes and Misdemeanours, volume 3 (1730):
[Lord Chief Justice.] It is notoriously known to all that have had any Dealing in London, or been acquainted with any thing there, that till within these six or seven Years last past, the Lord Mayor and Court of Aldermen, and the Common Hall used to go a birding for Sheriffs (you very well know what the Phrase means) and perhaps it was not once in ten times, that those that were chosen Sheriffs, held ; but generally every Year, there were I know not how many Elections upon sining off, or swearing, or some reason or other ; so that now and then there was but one Sheriff chosen for a great while together ; and now and then never a one from Midsummer-day till near Michaelmas. And the way was to consider, such a one hath most Money in his Pocket ; Oh, then put him up for Sheriff : And then, if he went off, then another would be found out. And there was one old Deputy Savage, that used to keep a black Book, that would furnish Names for I know not how many Elections. And who should be Sheriff, so as to divide into Parties, and Poll, was never a Question before such time as Mr. Jenks, that they speak of came to be put up, and there the Dispute began ; then the Faction began to appear.
A similar use involved casting someone in a stage role. From "Faithful Copies of Letters between Hopkins and Wild, Prompters to the Monopolizers," in Fugitive Pieces in Prose and Verse (1795):
Pray how shall we manage without Smith to-morrow? I depended on your lending him us for Harry the Fifth ; but now I fee you have put him up for Charles Surface. Cou'dn't you let him come to us and play two acts of Harry, as you don't want him in Charles till your third? And then Hull shall read the rest with an apology for Smith's being suddenly hoarse, sprained his ancle, &c. &c.
And yet another early meaning was to flush from cover (as a game bird or other animal). Thus from Charles Shadwell, "Irish Hospitality: Or, Virtue Rewarded," in Five New Plays (1720), we have this exchange between Sir Jowler Kennel (a "Country Baronet") and Morose (a "blunt honest Fellow"):
Sir Jowler. But come, who springs Sir Patrick for me ; you know his haunts, Morose, and ten to one can find him sitting.
Morose. Yes, yes, I can put him up for you, that you may run him down with your impertinencies.
The "store or make ready [a thing for future use]" appears first in John Parkinson, "Styrax arbor. The sweete Storax tree," in Theatrum Botanicum (1640):
It is called ... in Latin Styrax arbor, as the Gumme is called Gummi Styrax, or Storax, and in shoppes Storax or Styrax Calamita, which for what cause it was so called, Galen declareth, that because the best and most sincere came from Pamphilia, they used to put it into Canes, the better to preserve, not onely the sent as most say, but even the substance too, as I thinke, for the pure sincere gumme is so piersing that no barrell can be made so close, but that it will search the joynts, and draine through them, which opinion of mine although it may seeme strange, as not being heard of before, yet I have many reasons both to induce me thereunto, & some to contrary thwirs that object the transportation of handfuls of Dictamm, in Canes or Ferula stalks in the like manner, which are of far differing natures: the one a dryed herb, which need not any such inclosure, to preserve the sent, whereof it hath not so much that they needed so to put it up for feare of loosing, and besids the cask was so smal that abundance of them could containe but a little merchandize, some other cause they had surely, if they did put them, the leaves and stalkes I meane, into the Canes (whereof I somewhat doubt, but that they put them rather with Canes to keep them from breaking) & this other a gum that required some tight cask to containe it, for feare of leaking, and the Cane between the joynts, as not having any chinke, was the fittest with them I thinke to containe it, and thereof I thinke came the name of Calamita, to confirme which opinion, I have found the sincere gumme of Storax, which I have by Art and the presse onely (and not by any distillation) purified and made to be so pure that it would pierce even through a woodden vessell in the heat of Summer, and therefore was forced to keepe the said sincere gumme in a glasse or gally pot, which was so fluent that it would runne upon any small occasion of leaning down the vessell, a long time after the extracting.
One especially common form of the phrase in the early to middle eighteenth century was to "put [something] up for use" in cookery, as in John Nott, The Cooks and Confectioners Dictionary (1723):
To preserve Elecampane Roots. Wash and scrape the Roots very well, cut them to the Pith thin, and the Length of your Finger ; then put them in soak in Water for three Days to take away their Bitterness, and shift them twice a Day ; then boil the Roots very tender, and put twelve Ounces of clarified Sugar to every Pound of Roots, and boil them in the Sugar over a gentle Fire, till enough ; then take them off, and let them stand, and betwixt hot and cold put them up for Use.
In the nineteenth century, the phrase "put [something] up" could mean both "offer for sale at auction" and "render or offer," as we see in this excerpt from Samuel Lover, "Knocked Up and Knocked Down," in National Proverbs (by 1868), which plays on the phrase:
After several good animals had been disposed of, a very wretched hack was produced — a most melancholy specimen of horse-flesh — an over-worked jade, without a leg to stand on, and blind into the bargain. The auctioneer commenced, — "What will you allow me to say, gentlemen, for this horse? Well, give me a bidding yourselves — say any thing you like for him."
"Faix we can't say much for him," said a horse-dealer who was present, and sometimes did the facetious, hitting off a "good thing," while he struck a bargain, and indifferently cracking either his joke or his whip.
"What shall I put him up for? " said the auctioneer.
"He had better put him up for the crows," said the dealer, in an undertone to the by-standers, " for I think they always bid fair for such as him."