Long before it was associated with pumpkins, the term jack o'lantern was applied to the phenomenon called the ignis fatuus ("fool's fire," the flame that only fools follow or fear), the naturally arising burning of methane, or "swamp gas" over marshy ground. Calling it "jack o'lantern" was first recorded in the 1660's in England; and the first time it's application and use with a pumpkin was recorded in the United states was 1834, and then as a harvest or thanksgiving decoration. Only in 1866 to we see reference to it's use at Halloween.
There is "an old Irish legend" telling the origin of Jack O'Lantern. It says there was a farmer called Stingy Jack, a mean, lazy, but shrewd fellow who never did anyone any good. When the Devil came to take his soul, Jack fooled him into climbing up an apple tree to get him an apple for his last meal. While the Devil was up in the branches, Jack quickly drew a cross on it's trunk, depriving the fiend of his power and trapping him up the tree. Jack only let him down again when he promised to never take the farmer's soul to Hell.
The time came for Jack to die, and his soul headed up to Heaven. He was turned away from the gates, however, because he had never done a single good deed in his life. Seeking some final home for his soul, he wandered down to Hell, but the Devil, true to his word, refused to let him in the door. Jack's soul would have to travel without rest through the waste places of the world, until the end of time. After Jack begged for some light to guide his footsteps in the dark, the Devil mockingly threw him one of the ever-burning coals of Hell. Placing the ember inside a large turnip he had in his pocket and holding it before him, Stingy Jack began his weary wanderings as Jack-of-the-Lantern--or Jack O'Lantern, for short.
The use of large root vegetables for makeshift lanterns was common in the British Isles--the availability, ease, and disposability of them made them popular among the poor. You can still read old stories where people head out into the night with a large turnip full of coals. Turnips, beets, mangelwurzels--all sorts of roots grown large--could be used. Here is a turnip:
And here is a mangelwurzel:
But when immigrants came to America, they found the pumpkin, with it's large size, easy carvability, and generally hollow nature, to be a natural substitute for the old "turnip ghosts," and this is the form of jack o'lantern most of the world knows today. It's gargoyle grin and wierd glow light the night, frightening away less friendly spirits and startling the unwary with it's "fool's fire."