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.)