What appears to have happened is a 20th Century conflation of two different legends, one involving leprechauns and gold and another involving rainbows and gold.
There is really no evidence associating leprechauns with rainbows before the 20th century. (A different answer quotes a Time magazine article from 1952).
The sole folklore-related Google Books result from the 19th century containing both "rainbow" and "leprechaun" comes from Irish Melodies, a compendium of poems by Thomas Moore, but a look at the actual page is disappointing: the end of one poem mentions a rainbow while a footnote to the next poem mentions a leprechaun. It's just a typographical coincidence.
An 1851 book of Northern mythology talks about pots of gold at the ends of rainbows as coming from Germanic myth:
According to a popular belief in Germany, Denmark, and England, a golden cup or hidden treasure lies where the rainbow apparently touches the ground. This seems a remnant of the belief in Mimir's spring, in which wisdom's golden treasure was concealed.
-- Benjamin Thorpe, Northern Mythology, London, 1851, p. 158
Thorpe refers to Mimir's well, which lies near the Jotunheim end of the rainbow bridge Bifrost. No leprechauns here.
The Tree of Myth, an 1889 book of folklore by Charles de Berard Mills, states:
Children believe at this day that a golden cup or bag of gold lies at the end of a rainbow. The story comes from the ancient sun-myth so widely diffused, of the golden orb sinking into the waters of ocean or stream or lake. In one transformation it was the legend of a golden treasure buried in the Rhine, as we have it in the Niebelungen Lay, then finally, changed as it is in the nursery tale, we see the old myth again. No leprechauns here, either.
Leprechaun gold is well-hidden and guarded. It doesn't have a rainbow directing the whole world to its location:
If you could only catch the leprechaun at his work and hold him, he would tell you where the crock of gold, his hidden treasure, lies hidden. Nor would it turn into fairy-gold, once found. But the leprechaun is artful and plays shabby tricks sometimes. He was once caught by a peasant, and in return for his release indicated where a crock of gold lay. It was under a spike of ragweed in a thirty-acre field.
-- "Irish Superstitions, Spells, and Charms", Katherine Tynan Hickson, The Outlook , collected in Current Literature, 1895
Notice you don't find the leprechaun's gold just lying around at the end of the rainbow, you have to kidnap the creature and make him tell you where the gold is.
This is a good segue to what appears to be what I think is the point of conflation, which is the 1947 Broadway musical Finian's Rainbow, by E. Y. Harburg and Burton Lane. It was a smash hit that ran for 725 performances, and was later made into a 1968 movie starring Fred Astaire and Petula Clark.
Ever since I was 2, you've been seeing leprechauns and rainbows over your whiskey jug.
The play revolves around a pot of gold that Finian McLonergan stole from a leprechaun in Ireland, then brought across the Atlantic to Rainbow Valley, Missitucky. He hopes to bury it near Fort Knox in hopes the gold will multiply. But Og the leprechaun follows Finian to America trying to get his gold back.
Notice it's not said the gold was found at the end of the rainbow...instead, Finian brought the gold to the end of the rainbow. Nevertheless the opening number "Look To The Rainbow" uses the rainbow as a metaphor for a dream to be followed. All of the elements swirl together and it looks like that's how this entered popular folklore.