A Google Books search finds multiple instances of shill in the sense of "accomplice" from Robert Brown, "The Watch," a short story set in an auction in New York City, in The Metropolitan Magazine (April 1911):
The auctioneer passed the cheap glasses into the audience, looking after them fondly and retaining the leatherette case in his hand. "You are now looking at what is without doubt the finest, most beautiful piece of workmanship you have ever held in your hand. Genuine Lemier! You all know what that means! Why, gentlemen and ladies, it's the same as the word 'sterling' stamped on silver, or '18 caret' on gold. It's money in your pocket if you buy this. It's an investment. Every gentleman must have have one. I'm bid dollar only"—he took a bid from one of his "shills" (another name for bid-boosters) in the audience.
...
A derisive laugh went up from the well-trained shills [at the auction] and Dougherty condescended to smile, for deep down in every man is a fondness for the stable article, for the fine thing that will last a lifetime, not for the showy fashion to be discarded to-morrow.
The shill beside Dougherty handed the watch back to to him at that psychological moment. ...
"You'd start it [the bidding] for a trifle—five dollars, surely?" prodded the auctioneer in a manner so evident that the shills themselves would have blushed at the imposition, were they not as case-hardened to that kind of crime as the auctioneer himself.
...
Dougherty glanced at the shill opposing his real money with mind money. Let that tall, pasty-faced gink beat him, get that little gem of a jewel of a watch that belonged to Mame—never!
The earliest Google Books match for shillaber, meanwhile is from Word-Lore: The 'Folk' Magazine, volume 1 (1926) [combined snippets]:
In this case an old circus trouper is the speaker, and his remarks are taken seriously, and a circus "glossary" is provided. (This glossary, by the way, includes the following curious item:—
Shillaber—An employee of the circus who rushes up to the kid show ticket box at the psychological moment when the barker concludes his spiel. He and his fellow shillabers purchase tickets and pass inside and the crowd of towners in front of the bally stand are not slow in doing likewise.
With which lucid explanation of course we know all about the shillaber. But the glossary is silent as to barker and spiel).
Earlier than that instance is one from "Grafters Go Glimmering," in the Tonopah (Nevada) Daily Bonanza (May 29, 1920):
Tonopah will have a sane and sensible Fourth of July without the raucous barking of the shillaber of the street carnival. The people of Tonopah expressed themselves in no unqualified tone when they learned what was contemplated for the national holiday week and forthwith sent up such a protest that the American Legion refused to be a party to shielding the fakers and dropped all negotiations. Merchants on Main street refused to sign a petition for use of that thoroughfare and the citizens of Brougher avenue turned a deaf ear to all appeals from the circus crew for consideration.
And from a full-page ad for "Big Auction Lot Sale," in the [Ardmore, Oklahoma] Daily Ardmoreite (May 16, 1920):
GUARANTEE[:] A certified check for $5,000 has been put in the hands of the Mayor of Grandfield as a forfeit to be paid to anyone who will prove that that there are any by-bidders, cappers or shillabers on the grounds. Absolute aution sale and everything above-board.
And earlier still, from W.W. Chapin, "Success: San Francisco's Symbol," in the San Francisco [California] Call (January 1, 1913):
It is the popular thing these days for the smaller cities to adopt what they call a "slogan," slogan being the battle cry of a barbarian, the shibboleth, as it were, of a shillaber. "Watch Bugleville Grow" they cry. "See Squashville Swell," or "Bungtown Booms." Amusing as such war cries are still their uses are like those of the bass drum of the Salvation Army.
Anatoly Libermn, "Extended Forms (Streckformen) in English," in Studies in the History of the English Language II: Unfolding Conversations, cites The Oxford English Dictionary as having an example of shillaber from 1913:
Another word with stress allegedly falling on the first syllable is shillaber (American slang), of which the OED, The Second Supplement, has only one 1913 example. The lexicographers on the present staff of the dictionary could not have heard it, for it has been dead for almost a century, and only its doublet shill 'decoy or accomplice, especially one posing as an enthusiastic or successful customer to encourage other buyers, gamblers, etc.' is in use. Shill is probably an abbreviation of shillaber (so in the OED), whose origin is said to be unknown. The development from shillaber to shill does not prove that the longer word had initial stress: cf. prof from professor and, conversely, 'burbs from suburbs. Could shillaber be an extended form of Germ. Schieber 'black marketeeer' (*shi-la-ber)?
But unless the OED's instance from 1913 is the item from the January 1, 1913, San Francisco Call, the latter probably antedates the OED's example. In addition to this item, the Chronicling America newspaper database finds two matches from before 1913. From "Blacks May Get Together Next," in the [Grand Forks, North Dakota] Evening Times (September 12, 1910):
"The next big fight for the benefit of the Shillabers will be between Jack Johnson and Sam Langford. Don't overlook this. This match isn't so far away as you may think. I have it straight that Mistah Johnsing isn't doing so well in the theatrical line and I also know hat his financial state isn't any too healthy. ...
And from "Claims Men Are Fakers," in the Los Angeles [California] Herald (February 15, 1908):
Despite the warnings and repeated arrests by the prosecuting attorney, Edward J. Fleming, the barking peddlers of phony jewelry and jejeune junk, with other alleged peace disturbers, including cane-and-ring and similar rack gamblers, continue to ply their graft at Fifth and Main streets, in front of the Beaumont cafe, and also at Fifth and Los Angeles streets.
...
Frank Perkins, it is alleged, conducted a game in which the players tossed rings at silver money. Simpson and Dwyer are alleged to have been his assistants, known as "shillabers."
Also of interest is an item from 1915 that explicitly connects shillabers and shills. From "Says Summer Park Games Couldn't Be Beaten," in the Chicago [Illinois] Day Book (October 29, 1915):
The noble art of bunco—like tickling a man and picking his pocket—as practiced at Riverview is told by Jacob Le Bosky, attorney for some concessionaries of the park, in an action to investigate a receiver's report.
...
"The paddle wheels where candy and various other prizes were distributed with ever-r-y turn of the wheel were money makers. Some of them had 'shillabers' or 'shills,' employed by the owner of the concession.
"The 'shill' would buy a paddle and stand in the crowd with the rest. The man operating the wheel knew what numbers the 'shill' had on his paddle, so that when the wheel was turning, by means of a squeeze attached to the machinery, could stop it on a number which gave the prize to the 'shill.'
Conclusions
The term shill in the sense of "accomplice" goes back at least to 1911; and the term shillaber in the same sense goes back at least to 1908. An article published in 1915, when both terms were in active use, explicitly describes them as alternative words used to describe the same thing.
Usage seems to have spread fairly rapidly across the United States. By 1915, instances of shillaber and/or shill had appeared in periodicals in Los Angeles (1908), New York (1911), San Francisco (1913) and Chicago (1915)—but also in Grand Forks, North Dakota (1910).
Unfortunately, none of the early matches for shillaber gives any hint of where the term came from and what earlier word or person (if any) the term is based on. A New England humorist named Benjamin Shillaber had invented a character named Mrs. Partington, who became famous for such remarks as that she never worried about the price of flour because whenever she bought 50 cents worth, it always cost the same—but Shillaber died in 1890, and he seems to have contributed nothing toward the bunco arts.
Leo Rosten, who isn't shy about asserting Yiddish influences on U.S. English speech patterns and vocabulary, makes no claim for an association between shill or shillaber and any Yiddish word. I think this is another case where "origin unknown" continues to be the safest call.
J.S. Farmer & W.E. Henley, Slang and Its Analogues (1904) has the following entry for tootsie:
Tootsie, subs. (common).—A foot : spec. of women and children.
1897 MARSHALL, Pomes, 46. Towards her two TOOTSIES ... she gazed with a feeling of fear ... But her hose were well veiled from man's sight.
John Hotten, The Slang Dictionary: Or, the Vulgar Words, Street Phrases, and "Fast" Expressions of High and Low Society (1869) has this amusing entry:
TOOTSIES, feet, those of ladies and children in particular. In married life it is said the husband uses this expression for the first six months, after that he terms them HOOFS.
A Google Books search finds a first match for tootsies from Jane Weaver, "The First Baby," in The Peterson Magazine (February 1852):
"Did you ever see such a darling?" she [the mother] cried, tossing the infant up and down in her arms. "There, baby, that's ma's old friend, Jane. She knows you already, I declare," cried the delighted parent, as it smiled at a bright ring, which I held up to it. "You never saw such a quick child. She follows me with her eyes all about the room. Notice what pretty little feet she has: the darling footsy-tootsies,” and taking both feet in one hand, the mother fondly kissed them.
"Footsy-tootsies" makes another appearance in Charles Leland, Meister Karl's Sketch-book (1855):
Yes, this is fine weather for the juveniles ; and mightily do they enjoy it. The more aristocratic are now elaborately equipt in short-tailed frocks, with plaid gaiters on their little footsy-tootsies; and with a yard of broad ribbon behind, and a mighty hat with a trailing feather on their heads, are led forth, looking like hand-organ monkeys out for a walk, ...
The earliest instance I could find of tootsies being used to refer to the feet of a woman, rather than a baby or young child is in this memorable couplet from "The Periwinkle Girl" in Chambers's Journal (August 21, 1869)"
Both high and low, and great and small, fell prostrated at her tootsies ;
They all were noblemen, and all had balances at Coutts's.
The earliest instance in a Google Books search of Tootsie as a pet name for a girl or young woman is from R. Mounteney Jephson, The Girl He left Behind Him: A Novel (1876):
"Yes, I saw the daughter when I called," said Garstang. By Jove! sir, she fetched me uncommon! a devilish taking little thing, eh ? Why do they call her 'Clive,' though? Queer name for a she-male. Should have thought 'Flossie' or 'Tootsie' or something in that style would have been more in her line."
And the earliest instance where Tootsie appears as a lovey-dovey name for a sweetheart is from "A Guilt Chain," in Truth (December 25, 1880), based (it appears) on "Pat-a-Cake, Pat-a-Cake":
Happy thought! happy thought! Goldsmith's man,
Make me gold fetters as soon as you can!
Mould them, and beat them, and mark them A B,
And have them in order for Tootsie and me!
The form Toots appears as a girl's familiar name in S. Alice Callahan, Wynema: A Child of the Forest (1891):
It would seem as yesterday if Robin were not such a tall, broad-shouldered fellow, really towering over us all; and I, a cross-grained, wrinkled spinster; and Toots putting on young lady's airs—I suppose we shall have to call her Bessie, now; and even Winnie, our dear, little baby, is laying aside her dolls and—I really do believe it, Miss—is smiling at Charley or Willie or Ted.
So it appears that the expression from which toots eventually arose began as the (parental) baby-talk compound footsy-tootsie (meaning an infant's or child's foot), which subsequently appeared in the alternative forms tootsie-pootsie and tootsie-wootsy and in the shortened form tootsie; and from there the word expanded to apply to women's feet. By 1876 Tootsie was in use as a pet name for girls or women, and by 1891 Toots was.
UPDATE (January 12, 2017)
An Elephind newspaper database search turns up an early instance where "tootsie" appears as part of a baby talk description of an infant (and not specifically of the infant's toes). From "A Baby and a Merry Editor," in the [Oregon, Missouri] Holt County Sentinel (February 8, 1867):
"...And it [the baby] is ours to keep. We can watch it as it grows, and be glad when it learns to laugh, and sit on the floor, and to tumble over on its back, and put its big toe in its mouth, and to stand alone, and to walk, and to climb up on the table, and to cut holes with the scissors in its mother's dresses." "De sete 'ittle pootsey tootsie!"
Likewise, "A Proper Thing to Do," in the Tiffin [Ohio] Tribune (July 5, 1877), reprinted from the Washington [D.C.] Star, has this:
At a meeting of the Board of Public School Trustees last evening Trustee W. H. Browne, in presenting the list of teachers of the second district for confirmation, noticing that a large proportion of the first names terminated with the fashionable and foolish "ie," called attention to the fact and changed them to the proper names in each case, except that of Miss Dalton, who was christened Sallie. This was a proper thing to do. The Mamie, Nellie, Bellie, Mattie, Nannie, Sallie, Fannie, Jennie, Minnie, Virgie, Lollie, Mellie line of pet names may do for the ittie, tootsie, pootsie, pupils of an infant school, but when young ladies have reached years of discretion, entitling them to take the responsible position of teachers in our public schools, they should drop these tender nursery diminutives; and if they do not do it of their own volition the school Board should do it for them.
A person writing a letter to the editor of the New York Sun (January 20, 1871) signs herself "Madame Tootsie"—seemingly a pseudonym, but the name choice is unexplained, so its historical value is rather dubious.
A very brief glossary titled "Matrimonial Dctionary," originally printed in Punch but reprinted in the Bell's Life in Sydney [New South Wales] and Sporting Reviewer (March 27, 1847) has this:
Tootsy, Mootsy, and all words ending in tsy, are terms of great endearment. The exact meaning of them has never been ascertained. They are never heard after thirty.
...
Toodledums.—See Tootsy.
The term "footsy-tootsy's" shows up in the same newspaper less than six months later, on September 4, 1847:
A correspondent says, that he occupied a chamber separated from that of a married couple by a thin partition. One cold night he hard the rough voice of the husband grumble out—"Take away your hoofs!" to which the wife replied, in a querulous tone—"Ah! you did not speak so to me when we were first married—then you used to say to me, 'Take away your little hootsy footsy tootsy's!'"
This may in fact be the source of the jest passed along by Hotten in his Slang Dictionary 22 years later. Many other newspapers related the same anecdote over the course of the next decade.
In any event, it appears that tootsy/tootsie/toots has been around a very long time as a sort of infantalized expression of affection.
Best Answer
Early print occurrences of 'fuddy-duddy' and 'fuddydud'
As noted in JEL's answer, the earliest Google Books match for fuddy-duddy is from Ambrose Bierce, "The Haunted Valley," a story printed in the July 1871 issue of The Overland Monthly (published in San Francisco, California). The expression occurs twice in the story:
The sense of the expression here is ambiguous, as the man given to shouting "Old Fuddy-duddy!" "Old Terrapin!" and the like at his two oxen is a madman.
Another very early instance, cited in Peter Bengelsdorf, American English Idioms in the News: Meaning and Origin (2012) appears in T.H. Haskell, The New Gloucester [Maine] Centennial, September 7, 1874 (1875), page 114, quoting the remarks of Alfred Haskell, Esq., of Portland, Maine, recalling his childhood days in New Gloucester:
This is a particularly intriguing instance, since Alfred Haskell is recalling people from his childhood, and it seems probable that this Alfred Haskell is the same one noted in Will's Genealogy Blog as having been born in New Gloucester in 1817 and having died in Portland in 1906. That would put the likely date of the prank sign directing potential customers to the repair shop of "old Fuddyduddy" to sometime between 1820 and the early 1840s. This makes it a remarkably early instance, if accurately recalled by Haskell at the age of 57.
Aside from Bierce's example, the earliest match that a Google Books search turns up is for the related term, fuddydud. From "The 'Fuddydud'," an editorial in California Knapsack (1892):
The earliest Google Books match for fuddy-duddy where the term clearly has the meaning "person set in his ways and out of tune with modern trends, fashions, methods, or styles" appears in a circular issued by C.B. Cottrell, reprinted in Printer's Ink (November 25, 1896) as "Dry Rot":
The earliest Elephind match for fuddy-dud is eight years older than its earliest instance of fuddy-duddy. From "Honesty vs. Policy," in the Door County [Wisconsin] Advocate (June 14, 1890):
This item appears without byline or attribution, but I note that the same language appears in the "Calendar for the Week" in the South London [England] Press (December 30, 1865), in a search of the subscription-only British Newspaper Archive (to which I do not have a subscription. The next match for fuddy-duddy or fuddydud that the British Newspaper Archive finds, however is from the 1940s, so this 1865 occurrence is quite mysterious.
Elephind's earliest match for fuddy-duddy is from a letter to the editor of the [New York] Sun from a Boston reader (September 2, 1898):
Subsequent instances of fuddy-duddy (or fuddyduddy) appear in rapid succession. From "Straining at a Gnat and Swallowing a Mastodon," in the Cambridge [Massachusetts] Chronicle (February 18, 1899):
From "High-Spirited Queen," in the Salt Lake [City, Utah] Herald (January 8, 1900, reprinted from the Boston Herald]):
From "Vivacious Plea for Realism," in the Indianapolis [Indiana] Journal (March 30, 1902):
And from the Kate Masterson, "The Decline of Angelhood," in the [Washington, D.C.] Evening Star (November 5, 1905):
One early instance of fuddydud suggests that the term may have been in use as a popular name for some type of confection. From "Young Andy's Pocket," in Little Folks (March 1901):
I have found no other mention of fuddydud as the name for some sort of sweet treat known to children in the early 1900s.
Early glossary definitions of 'fuddy-duddy'
The term fuddy-duddy appears in two glossaries recorded in one bound edition of Dialect Notes first in "Rural Locutions of Maine and Northern New Hampshire," in Dialect Notes, volume 4, part 2 (1914):
And again in "Terms of Disparagement in American Dialect Speech," in Dialect Notes, volume 4, part 3 (1915):
The citation to Dialect Notes, volume 3, yields an entry from around 1910 that combines the two definitions mentioned above:
Unfortunately this volume of Dialect Notes seems to be available only in snippet view, so we don't have any context for the glossary in which it appears.
Harold Wentworth, American Dialect Dictionary (1944) identifies early twentieth-century use of the term in several parts of New England, extending to New Jersey in the Mid-Atlantic region:
One of the most surprising things I encountered in my research was the absence of fuddydud and fuddy-duddy from the J.S. Farmer and W.E. Henley, Slang and Its Analogues, Past and Present. Volume 3 ("Fla. to Hyps.") of this seven-volume work was published in 1903, after practically all of the citations listed in this answer had been published—and yet it overlooks the term completely. Still, it may be of some value to note the slang terms in the vicinity of fuddy-duddy that Farmer & Henley does identify, in case they may provide a clue to the origin of the missing term. Here they are:
None of these terms seems at all close to any of the cluster of notions comprehending "a busybody, a codger, a person of obsolete ideas, an old and ineffectual person" that dominate the earlier usage of the term. Much closer to the mark is fiddle-faddler, noted in Farmer & Henley's entry for fiddle-faddle:
A fuddy-duddy, as the term has been widely understood and used over the years, may be a trifling, fussing person given to talking rot and making much cry and little wool. Nevertheless, I have not found any reference work that connects fiddle-faddle[r] to fuddy-duddy, and I haven't found any evidence that the two words are etymologically related. The similarity in meaning may simply be coincidental.
Another noteworthy absence of fuddy-duddy is from Eric Partridge, A Dictionary of Slang and Unconventional English, which has no entry for the term (or its allies) at least as late as the fifth edition (1961)—a major challenge to the hypothesis that the term originated in that form in England, since Partridge focuses primarily on British slang. The eighth edition of Partridge (1984) has this entry:
Partridge may be right that fuddy-duddy spread through Britain in the 1940s as a result of exposure to U.S. usage, and that fuddy-dud as used in Australia was independently derived from U.S. fuddy-duddy in the 1950s; but fuddy-dud existed in the United States and possibly in England in the nineteenth century, and it is not entirely clear that the term originated in North America.
Recent dictionary entries for 'fuddy-duddy'
The American Heritage Dictionary of the English Language, fifth edition (2010) has this entry for fuddy-duddy:
Merriam-Webster's Eleventh Collegiate Dictionary (2003) has this:
And The Concise Oxford English Dictionary, tenth edition (2002) has this:
Where did 'fuddy-duddy' originate?
The examples noted in my answer strongly suggest that fuddy-duddy in that form is of North American origin. The earliest instance of the term that I found (from 1871) is from "The Haunted Valley," a story by Ambrose Bierce, who was born in Ohio, but had been living in San Francisco for at least five years when he wrote "The Haunted Valley." Subsequent published nineteenth-century instances of the term originated from California, Wisconsin, Indiana, New York, Massachusetts, and Washington, D.C. And according to both Dialect Notes and Harold Wentworth's American Dialect Dictionary (1944), the term was especially prevalent during the earliest decades of the twentieth century in New England.
A contrary possibility is that it emerged from the northern English dialect term duddy fuddiel, as suggested by Jonathon Green, Cassell's Dictionary of Slang (2005):
The Cumberland connection noted by Green is undoubtedly William Dickinson, A Glossary of the Words and Phrases of Cumberland (1859):
An earlier entry in the glossary notes that duds means "clothes" and that "Bits o' duds" refers to "the scanty wardrobe of indigence."
It is certainly possible that duddy fuddiel meaning a ragged fellow migrated from Cumberland to the United States in the early 1800s and evolved into fuddyduddy meaning an old codger. But I have been unable to find any instances of duddy fuddiel (or of duddy or fuddiel in the relevant sense) in U.S. sources. A further complication is the isolated but impressively early 1865 instance of "old fuddy-dud" in a seemingly modern sense in a London newspaper—an article that seems to reappear, uncredited, 25 years later in a Wisconsin newspaper. If the hypothesized transformation from duddy fuddiel to fuddydud[dy] occurred in England, it left the very faintest of trails.
Most intriguing of all is the 1874 reminiscence about "old Fuddyduddy" at a reunion in a small town in Maine that seems very likely to refer to a person and an incident from the 1840s or earlier. That instance suggests that fuddyduddy existed as a dialect term in New England in perhaps the modern sense of "old fogey" in the first half of the nineteenth century. How it got there, however, is by no means clear.