The origin comes in two parts. The first part is that the phrasing is inspired by the Bible, particularly Genesis 28:12 (for stairway to heaven) and Matthew 7:13 (for highway to hell).
The second part is tracking the early usage of this phrase in English. This poses some difficulty, because while highway and stair as words have been used since Old and Middle English, stairway is first attested in the 18th century (OED 1, 2 3). Also, early translations of Genesis 28:12 only use ladder, not stair (let alone stairway), and early translations of Matthew 7:13 emphasize that "broad is the way" but don't refer to it as a highway, let alone a highway to hell. So if we are looking for the origin of these phrases, we cannot rely on early Biblical translation or the English vernacular. Instead, evidence comes from larger corpuses of texts.
Stairway to Heaven
Searches for stair suggest that the concept (but not the phrase) were present before the 19th century. For instance, Samuel Rutherford in Mr. Rutherfoord's Letters (1724; accessed on Eighteenth Century Collections Online) describes how Jesus "hath numbered all the steps of the stair up to heaven" (p. 461).
The exact phrase develops in the 19th century as an allusion to multiple ways to Heaven, including both the Tower of Babel and Jacob's Ladder. The first instance of the phrase in Google Books comes in an article published in The New Jerusalem Magazine in 1867, in what is not a reference to Genesis 28:12 but perhaps an allusion to Genesis 11 and the Tower of Babel:
He is listening to the voice of the serpent, building his tower as a stairway to heaven, and trying to force the camel through the needle's eye.
An article in United and Reformed Presbyterian Pulpit from 1868 has a similar usage:
The unfinished Babel that he attempted to rear as a stairway to Heaven ...
There are also more generic usages, like this one from a story in Chetham Miscellanies from 1872:
But a more modern writer has given us his idea of another scala coeli, or stairway to heaven ...
Finally, the first direct allusion to Genesis 28:12 comes with an 1891 guide on Sunday school lessons:
From Paul's prison in Rome there arose, as from Jacob's pillow of stones at Bethel, a golden stairway to heaven, with messenger angels ascending and descending it.
Highway to Hell
The first instance of Highway to Hell in Early English Books Online comes from a 1612 text titled Conceyted letters by Nicholas Breton:
SYr, I heare by some of my acquaintance that you goe
on apace with the World: I pray GOD you go
as fast towards Heauen; but by the way let me tell
you, what I thinke fittest for you, now and then to haue
minde of, least you forgette the mayne, while the bye∣way
deceyue you: for what is Honor without vertue?
King Dauid tells you, it is but a blast: meaning a
prowde man: and what is Wealth without Wise∣dome,
but Couetousnesse? and that is the toole of all
euill: and what is Life without Grace, the very high∣way
to Hell?
The rhetorical effect of this sentence is to compare the mayne (the straight and narrow path) with the byeway through several examples. Life without grace becomes "the very highway to Hell." Several other sources are attested in the same century, including one that connects the phrasing back to Matthew 7:13's idea of the broad path (Samuel Rowlands, Heavens Glory, Seeke It, 1628):
that sinne, that broad way-path and highway to hell,
There are many results for the phrase from this point onwards.
