I have some notes to supplement ermanen's very well-researched and wide-ranging answer to this question. They don't constitute a freestanding answer, in my opinion, but they do offer additional context for several of ermanen's quotations, as well as a few new reference points.
Early occurrences of 'alakazam and 'allakazam'
The earliest occurrences of alakazam in the Library of Congress's database of U.S. newspapers is this excerpt from an anecdote originally in the Indianapolis [Indiana] Journal, reprinted in the Salt Lake [City, Utah] Herald (June 5, 1896):
"It's been two year now," said he [a suddenly wealthy hardscrabble farmer], "sence we struck gas on the farm, and I ain't had a quare meal sence. Been fillin' up on Charley horse rusies, soofay de alakazam, an' all them French dishes ever sence. That's what comes of marryin' a woman who believes in keepin' up with the percession when you got the price, as she puts it.
It appears, though, that this instance may have been a typographical error by the Herald's staff, since five other newspapers that reprinted the same Indianapolis Journal article used the spelling "allakazam" (and two words earlier the spelling "sooflay"): the New York Tribune (May 24, 1896) [this is the version cited in ermanen's answer], the Cottonwood [Idaho] Report (July 3, 1896), the Red Lodge [Montana] Picket (July 4, 1896), the Pascagoula [Mississippi] Democrat-Star (August 7, 1896), and the [Honolulu, Hawaii] Independent (November 10, 1896). Indeed, the original Indianapolis Journal article titled "A Wild Revel" (May 19, 1896), which is preserved in the Hoosier State Chronicles newspaper database, spells the word allakazam. This is the earliest instance of the double-l spelling of the word that I've been able to find—and the next unique instance of allakazam that the Library of Congress database finds doesn't occur until 1918, when it appears as the fictitious name of a Middle East city governed by a Grand Vizier, in a story in the Topeka [Kansas] State Journal.
The same early instance in which alakazam is used as part of a magic incantation that ermanen's answer reports as appearing in the Baltimore [Maryland] Sun of March 30, 1902, also appears on the same date in the Salt Lake Herald; it's from a story by Walt McDougall titled "Little Howard Megargee Finds a Magic Charm That Cures His Dying Father and Turns Their Enchanted Cat Into a Lovely Princess."
However, an Elephind newspaper database search turns up a substantially earlier instance of the word used repeatedly as an expression of great enthusiasm. From "Among the White Tents," first published in the Chicago [Illinois] Herald Tribune and reprinted in the New York Clipper (July 14, 1888):
We're goin' to de cirkis! / Alakazam! / To see de ringtailed monkey / Ride on de spotted donkey! / Oh , golly! aint dat hunkey? Alakazam!
Jist like Its on de show bill! / Alakazam! / De lady an' de cannon! / De Japanezers fannin', / An' on dere chins a stan'n'! / Alakazam!
An' all wots in de street p'rade! / Alakazam! / De clown! say, don't dey buzz him / When dat dere trick mule 'does him'? / You bet I wish I wuz him! / Alakazam!
De lemonade and peanuts! / Alakazam! / Under de canvas? Oh, no! / Right trew de big door WE go! / An' den! we whitles 'you know'! / Alakazam!
The newspaper item says that the poem is "dedicated to Col Geo. O. Starr, Barnum & Bailey's newspaper man, at the free circus performance for the newsboys of Chicago." Notable by its absence from the poem is any reference to a magician or to magic tricks.
Early occurrences of 'alagazam' and 'allagazam'
A Google Books search for "alagazam" produces one very early match (also cited in ermanen's answer). From "Whimsicalities" in The Hawaiian Monthly (May 1884):
At this point the conversation [in which one of the participants was more than liberal in sprinkling his speech with pretentious words out of Latin and Italian] was interrupted by the tones of a deep, rich bass voice belonging to a gentleman who sat directly behind the alagazam idiot:
"Asinus, asini, asiniorum."
The intended sense of alagazam here is difficult to pin down. It could mean "perfect" (as in "perfect idiot"), or it could mean any number of other things that are less flattering as stand-alone adjectives.
An Elephind search yields this match for alagazam from "A Los Angeles Idyl" in the Los Angeles [California] Herald (March 11, 1888):
When clang, clang, clang, rip it and bang. / Bingbang, bingbang, alagazam, / Twist us double, Ring us about. / Kling, kling, klingklang, kerflop, kerslam, / Clang, clang, clang, clang, hoop it and lam. / Yank our tongues out, give us a bout, / Bing, bing, bingbang, bif, bif, kerflam, / Clang, clang, clang, clang, rattle and ram, / Shiver our timbers and knock us out, / Rang the big and the small bell / Of the quaint, old cathedral.
The instance here is evidently nonsensical or onomatapoeic, but nevertheless indicates some familiarity with the sound, if not the sense, of the word.
The earliest instance of alagazam (or allagazam) in the Library of Congress database is this one from the [Phoenix] Arizona Republican (October 21, 1897), mentioning what it calls a "four-in-hand machine song" titled "Al-la-ga-zam" as part of an evening of musical variety entertainment:
The introduction of excellent singing specialties in the second and third acts of "Tony the Convict," on Friday night, will render the performance doubly enjoyable. Miss May Phillips will sing "Sally Warner," on of the latest eastern hits; H. Clay Parker will be heard in "coon" melodies; the four-in-hand machine song, "Al-la-ga-zam" will create a furore, and Fred Mussey's character songs will take the house by storm. Included in his repertoire will be a new topical song, "When Some One Pulls the String," with some "warm" extra verses by a local author, and a plaintive love ditty, "What Would Duckey Do if Lovey Died?" The performance will be one of the most entertaining ever seen in Phoenix.
The interesting thing here is that the song "Al-la-ga-zam" is being performed four to five years before Abe Holtzmann published his hugely popular song "Alagazam" (cited in ermanen's answer). Most of the matches for alagazam in the Library of Congress database involve Holtzmann's song, which was regularly performed at band concerts, as a march, a rag-time, a two-step, or a "cake walk."
A second instance of alagazam before 1902 appears in the Seattle [Washington] Post-Intelligencer (February 4, 1900), in the context of a joke-name for a Michigan town (probably based on Kalamazoo, Michigan):
The organized bodies which always attend the national conventions will be bitterly disappointed in the [Philadelphia] convention hall arrangements. Their favorite performance i to march into the hall headed by a brass band with banners flying. There won't be room at Philadelphia for any brass band except the one hired to fill in pauses between the speeches. and the McKinley Club of Alagazam, Mich., will find a cold reception when it tries to enter the convention hall in a body.
Since Alagazam is not an inherently funnier word than Kalamazoo, I suspect that the decision to use it in this story reflects some other association that alagazam already (in 1900) has in readers' minds.
Also difficult to explain is this entry in Louise Pound, "Word-List from Nebraska (III)," in Dialect Notes, volume 4, part 4 (1916):
alagazam, adj. Fine, excellent. "The jelly was alagazam." See also elegazam, below.
...
elegazam, adj. Variant of alagazam, above.
Along the same lines, H.L. Mencken, American Language Supplement 2 (1948) notes that among textile workers of that day, elegazam meant "perfect work."
