“What in tarnation?” is one of a wide variety of euphemistic expressions of surprise, bewilderment or anger that arose in 18th and 19th century America. Perhaps due to our Puritan legacy, Americans were, during this period, especially creative in devising oaths that allowed us to express strong emotions while still skirting blasphemy.
Such inventions as “heck,” “drat,” “darn,” “gosh,” “jiminy,” “gee-whiz” and “goldarn” were all devised to disguise exclamations that would have been considered shocking in polite society. “Sam Hill,” for example, is simply an early 19th century euphemism for “hell” (and while there have been many people named Sam Hill throughout history, the expression does not come from the name of any particular Sam Hill).
“Tarnation,” which dates back to the late 18th century, is an interesting example of this generation of euphemisms because it’s actually two euphemisms rolled into one word. The root of “tarnation” is “darnation,” a euphemistic modification of the word “damnation,” which at that time was considered unfit for polite conversation. “Darnation” became “tarnation” by being associated in popular speech with “tarnal,” an aphetic, or clipped, form of “eternal.”
It may seem odd that “eternal” would ever have been considered a curse word, but to speak of “the Eternal” at that time was often to invoke a religious context (God, Heaven, etc.), and thus to label something or someone “eternal” in a disparaging sense (“You eternal villain!”) was considered a mild oath. Shakespeare, for example, used “eternal” in this way in at least two of his plays.
So at some point someone, probably in a moment of exasperation, mixed “darnation” with “tarnal,” and we ended up with “tarnation.”