The earliest instance of "blue blazes" that I've been able to find occurs in Piomingo [John Robinson], The Savage (1810). In fact, it appears twice in this book, once as "the blue blazes of Tophet" and once as "the blue blazes of hell":
Devil. But that, which displeases me more than anything else, is their habit of attributing to me the origination of a thousand pitiful sneaking little criminalities, with which, I swear by the blue blazes of Tophet, I would not dirty my fingers. My conscience is, certainly, not very troublesome; but I indubitably would not debase my infernal dignity so much as to assist in the perpetration of a thousand little meannesses to which men are addicted.
"I have said the word," says I, "madam," says I; "and my word's as good as my bond," says I. "I'll go," says I, "if ten thousand devils were to rise," says I, "and spurt the blue blazes of hell in my face," says I, "Tom! fetch out my horse."
Robinson was evidently from Tennessee, and his usage seems colloquial and (to judge from its repeat appearance) at least personally habitual.
It next appears in Mason Weems, The Drunkard's Looking Glass: Reflecting a Faithful Likeness of the Drunkard, in Sundry Very Interesting Atitudes, (1812/1818), as cited in Hachi's answer:
YE STEEP DOWN GULPHS OF LIQUID FIRE! YE BLUE BLAZES OF DAMNATION!——But hush, thou false zeal, hush! and curse not him whom Christ hath commanded you to pray for.
Here the "blue blazes" seem to refer to the alcohol itself. And indeed both methanol and ethanol burn primarily with a blue flame. As this excerpt indicates, Weems's book is cautionary to the point of didacticism. Wikipedia reports that Weems was a clergyman and author, originally from Maryland; he is best known for his early (and not terribly reliable) biography of George Washington, which may have been the source of the "I cannot tell a lie" cherry tree story.
The third-earliest mention of "blue blazes" that I've been able to find is from 1814 and arises in the context of a dream about being dragged to hell by overpowering devils. From Lorenzo Dow, History of Cosmopolite : or, The Four Volumes of Lorenzo's Journal (1814):
And when I got within sight of hell, to see the blue blazes ascending, and to hear the screeches and groans of devils and damned spirits, what a shock it gave me, I cannot describe : I thought that within a few moments, this must be my unhappy lot.
Wikipedia describes Lorenzo Dow as "an eccentric itinerant American evangelist, said to have preached to more people than any other preacher of his era." The dream he relates occurred when he was about 14 and profoundly affected his religious views. The phrasing seems to be primarily descriptive (the blazes in his dream were blue) rather than primarily alliterative.
All three of the books cited in this answer were quite popular in their day and may have contributed to the popularization of "blue blazes" in the United States. I can't deduce from these three early examples whether the expression originated in brimstone sermons or in the colorful colloquial speech of US post-colonials. Both areas of usage may have helped propagate the expression.
The fact that both sulfur and alcohol burn with a blue or primarily blue flame is not irrelevant to the early instances of "blue blazes" noted here, but I would hesitate to endorse Chapman & Kipfer's assertion that the connection between the expression and sulfur's flame color explains its origin dispositively.
And as various others have noted, alliteration surely played a role in enhancing the phrase's appeal, as well.