Wordorigins.org

This is an American euphemism for hell that usually appears in the form what in the Sam Hill? The origin is unknown, but the hill is undoubtedly an alteration of, or at least influenced by, hell. It also may have originally referred to the devil, as opposed to hell. If so, it would follow in a long line of personifications of the devil, such as Old Nick or Old Scratch.

The term appears in 1839, when it is recorded in the Havana Republican (NY) of 21 August:

What in sam hill is that feller ballin’ about?

(Source: Oxford English Dictionary, 2nd Edition)