My non-working link above is from the noted OED lexicographer and etymologist, Michael Quinion, so more than likely to be right. He gives a reference to the words of Sir John Beaumont: "The holy smoke of fervent prayers" dated 1627. The idea here is that the smoke of a burnt sacrifice or of incense 'carries' prayers heavenwards. However, Quinion claims that the phrase seems to have been 'reinvented' in the USA in the late 19th century at about the same time as 'holy terror', 'Holy Joe' etc, since it clearly has more in common with them than the old religious concept. In the same way, 'holy' cow' was created in the 1940s.