The spelling "fair do's" goes back well into the nineteenth century. The two earliest Google Books matches are from 1868 and 1872. From C.A. Wheeler, Sportascrapiana: Facts in Athletics, second edition (1868):
"You're not going to run like that surely, sir. Pull off that waistcoat at all events," said "Professional"—"and then yer trousers are such that no man could run in 'em." "Professional" was a right good-hearted fellow, and wished to see the youth start on what he called "fair do's." "All right, that'll do," said the young gentleman.
And from "Wilfred Wildblood," in The Raven Club Papers (1872):
You know, it was understood from the first between us, that nothing but death itself should separate us, and as we went 'fair do's' in every mortal thing, there wasn't much fear of our splitting.
Likewise, Henry Smith, "A Glossary of Words in Use in the Isle of Wight" (1881) uses that spelling:
Fair-do's, fair treatment. 'I thinks it's pretty well fair-do's.'—[collected at Newport]
As for the earlier variants noted by Hugo in his answer, the first occurs in a sports setting. From Thomas Hughes, The Scouring of the White Horse Or, The Long Vacation Ramble of a London Clerk (1859):
I suppose there are more unsettled points in wrestling, or it is harder to see whether the men are playing fair, for the crowd was much more excited now than at the backsword play, a hundred voices shouting to the umpires every moment to stop this or that practice. Besides, the kicking, which is allowed at elbow and collar wrestling, makes it look brutal very often ; and so I didn't like it so much as the backsword play, though the men were fine, good-tempered fellows, and, when most excited, only seemed to want what they called " fair doos."
A second early instance of "fair doos" appears in Edward Burlend, Amy Thornton, or, The Curate's Daughter (1862):
"Exactly; and now will you be kind enough to say what arts she practised on you to induce you so to feel [the need to kiss her]. Giddy girls sometimes tease young men, so that it is next to impossible for them not to notice them. Mind you, I am not blaming you so much as Amy, but I want to be at the bottom of it."
"I see you do, ma'am ; but let us have fair doos. It would not do to throw the blame on Amy for a thing she has not done, would it, ma'am? and I tell you the honest truth when I say she's never done anything of the kind. She could not help it."
And (again cited in Hugo's answer) from C. Clough Robinson, The Dialect of Leeds and Its Neighbourhood (1862):
DEW or DUE. "A shabby dew," says a man who has had twopence given him for getting a waggon-load of coals in. "A fairish dew," says another who has got a shilling and a lot of victuals away with him for the same. "A pock-arr'd dew"—being defeated in one's object; comes off the worst, and after a sorry fashion. It will be seen that these examples do not carry the shade of meaning "due" does in standard usage.