Wentworth & Flexner, Dictionary of American Slang (1960) suggests an extended Irish term:
shenanigans n.pl. Tricks, pranks, nonsenses; petty cheating or deception. Since c1870; may be from the Irish "sionnochwigham" = I play tricks.
The same source lists "shenanannygag" (also meaning a trick or prank) as being based on shenanigans and "not common."
Chapman & Kipfer, Dictionary of American Slang, Third Edition (1995) bump the origin to "by 1855" and retain the Wentworth/Flexner suggestion that the word perhaps comes from sionnachuighim "play tricks, be foxy."
The Facts on File Dictionary of Word and Phrase Origins (1997) begins its entry with this sentence:
shenanigans. Though now it is always used in the the plural, this Americanism for "mischief" or "trickery" was first recorded as shenanigan in 1855 in California.
I suspect that the citation in question involves a story from the California Herald cited in numerous Google Books periodicals, such as this one from the Merchants' Magazine and Commercial Review, volume 40 (1859), in which the following sentence occurs:
Jim took his bill, and eyeing the puzzled landlord as though he suspected some "shenanigan," he broke out—
"I want to see them 'ar books."
The earliest Google Books occurrence of this anecdote is in Yankee-Notions, vol. 5 (1856), but unfortunately the snippet view of this version of the story doesn't include the relevant term within its window. [Note (added 7 October 2015): As Hugo points out in a comment below, the relevant text from the December 1856 issue of Yankee-Notions appears in a Hathi Trust copy of that periodical.]
ADDED TO ANSWER (1/3/14):
Not surprisingly—considering its date of publication—John Russell Bartlett, Dictionary of Americanisms (1848) doesn't include an entry for shenanigan or shenanigans. But I was somewhat surprised that the second edition of this book (1859) has no such entry either. I haven't been able to find a copy of the third edition. The fourth edition (1877) does have shenanigan, along with this interesting discussion of the equivalence of shenanigan, skullduggery, and hornswoggle:
The "Philadelphia Times" (Nov. 5. 1877), in defining the word skullduggery [which Bartlett calls "a very good and very common word in the West"], says, "Its best Eastern equivalent is shenanigan, although the less complicated word hornswoggling [which Bartlett also identifies as "Western"] rather directly translates it."
This quotation suggests that shenanigan had become popular enough in the Eastern United States by 1877 for Easterners to consider it commonplace in (and perhaps even native to) their region.
Another early discussion of shenanigan (though spelled with a fourth n) occurs in Maximilian Schele De Vere, Americanisms: The English of the New World (1872):
Shenannigan, probably a purely fictitious word (though a Dutch origin has been claimed for it), frequently heard in the South and West, and denoting groundless bragging for the purpose of getting the better of another. "Shenannigan means any kind of chaff, foolery, nonsense, advanced to cover some little scheme or game." Hence Miss Vinnie Ream, the artist, whose skill was said to have been largely measured by her personal charms, was recently admonished by a writer in the Chicago Evening Post to "go to work and try better next time, instead of fooling members of Congress by a pair of black eyes and a mass of beautiful curls. No shenannigan, Vinnie!" (January 1871.)
FURTHER UPDATE (7/30/16):
An Elephind search turns up four occurrences of shenanigan in a California newspaper between July 10, 1854, and January 1, 1855. From "By Telegraph to the Union" in the Sacramento [California] Daily Union (July 10, 1854):
San Joaquin Democratic Convention. Stockton, July 9th, 1854. The Democratic Convention held in this city yesterday passed off with considerable jarring, and no few discordant notes. There was considerable "shenanigan" going on amongst them, and it is hardly supposable that the ill-feelings engendered are yet quieted down.
From "Postscript: San Francisco Correspondence," in the Sacramento [California] Daily Union (November 16, 1854):
After a few important preliminaries, a committee consisting of the following gentlemen were named to superintend the drawing, to see, as it was facetiously expressed by one of the "gods," that there was no "Shenanigan" about it, namely: Geo. H. Hoasefross, J. L Van Bokkelen, T. K. Battelle, Marshal McKenzie. W. H. Patten, F. M. Pixley, F. E. R. Whitney, R. B. Quayle, ...
From "The City: Pedestrianism" in the Sacramento [California] Daily Union (December 26, 1854):
The rival pedestrians, Wheeler and peeler, are making a great ado about walking a plank for one hundred and two consecutive hours. We can point to some clothiers on J street, in this city, who have been walking the planks in front of their stores, for a customer, for the past month. The exercise—they so regard it—is taken in full view of the populace, and conducted without any "shenanigan."
From "The City: Pastime" in the Sacramento [California] Daily Union (January 1, 1855):
Purse, ten dollars. Match, the horse to pull a lock-wheeled wagon weighing 2,390 pounds, and four persons more than the mare could. The preliminaries were arranged, after much confab, as follows: "Get away from that wheel we don't want any shenanigan—wheel ain't chucked—lift and see—stand back in front—here's four big men in the wagon (from an insider)—get in the center—two behind and two before—even on heels—turn that wheel up—take off that chain—don't let that horse run off with us (inside again)—&c."
The term also appears as a verb, in "Law Report: Twelfth District Court," in the [San Francisco, California] Daily Alta California (June 19, 1855):
A. D. Brown, witness for plaintiff, testified that he had had a conversation with the defendant, Zane, in which Zane said that the plaintiff had been trying to "shenanigan" him; that if he, Zane, failed in the action, he intended to have some satisfaction anyhow; that he had employed Judge Heslep as his counsel; that Heslep was an enemy of Satterlee's and hated him; that if Heslep could not gain the suit, he would at least give Satterlee a good "blackguarding."
It thus appears that shenanigan may first have been used in print in 1854 in a string of articles in the Sacramento Daily Union, where it seems consistently to have had a meaning along the lines of "fraud, deceit, or dirty trick playing."
