The night before All Hallows' Day (the original name for All Saints' Day, November 1st) is called 'All Hallows Even' or 'All Hallows' Eve'. 'All Hallows' Even' was shortened to 'Hallow-e'en' byt the 16th century, and the rest is history.
Oh dear, you may think, there's one of those errant apostrophes that slobs sprinkle throughout the language. Why would the dictionary give in and enter that apostrophized monstrosity? Surprise: that apostrophe is actually original to the word.
When Halloween first came into written use in English, October 31 wasn't the linguistic focus — November 1 was. In the western Christian liturgical calendar, November 1 is All Saints' Day, a feast day to honor all the Christian saints. But All Saints' Day wasn't called All Saints' Day until the 16th century. Prior to that, it was known by the name we borrowed from Old English: All Hallows' Day or All Hallows'. Hallow comes from the Old English adjective halig, which means "holy."
All Hallows' used to be a bigger deal — one 17th-century source notes that "the three grand days are All-hallown, Candlemass, and Ascension day"—and since important feast days usually started the night before with a vigil, the evening before All Hallows' gained its own notoriety as All Hallows' Even or All Hallows' Eve. All Hallows' Even was shortened to Hallow-e'en by the 16th century. The word Hallowe'en began to lose its apostrophe in the 18th century, though we still have some evidence for the apostrophized version.
That explains the name — but how do you explain the costumes, the candy, the jack-o'-lanterns? The original date that the early church chose for All Saints' Day was in the spring, but in the western church, it was moved to November 1 in 835 by Pope Gregory IV. This date just happened to coincide with the Celtic festival of Samhain, which marked the end of the year and the commemoration of the dead. It was believed that, during Samhain, the boundaries between the living and the dead thinned, which made it easier for the souls of the departed to visit the living.
Many Halloween traditions, like wearing masks, telling ghost stories, and carving vegetables into lanterns, sprung directly from Samhain celebrations. The Church contributed to Halloween celebrations as we know it, too: an activity called souling, when a person would go from house to house asking for cakes in return for praying for the souls of those in the house, was popular during the later Middle Ages, and may be the inspiration for our modern-day trick-or-treating.
Late-night viewings of Young Frankenstein and the traditional rejection of the gross candy from one's trick-or-treating bounty are not part of the historical Celtic or Christian celebrations of the day, however.