In medieval times, one popular All Souls' Day practice was to make "soul cakes," simple bread desserts with a currant topping. In a custom called "souling," children would go door-to-door begging for the cakes, much like modern trick-or-treaters. For every cake a child collected, he or she would have to say a prayer for the dead relatives of the person who gave the cake. These prayers would help the relatives find their way out of purgatory and into heaven. The children even sang a soul cake song along the lines of the modern "Trick-or-treat, trick-or-treat, give me something good to eat." One version of the song went:
A soul cake!
Have mercy on all Christian souls, for
A soul cake!
There is also some evidence of trick-or-treat type activities in the original Celtic tradition. Historians say the Celts would dress up in ghoulish outfits and parade out of town to lead the wandering spirits away. Additionally, Celtic children would walk door to door to collect firewood for a giant communal bonfire. Once the bonfire was burning, the revelers would extinguish all the other fires in the village. They would then relight every fire with a flame taken from the Samhain bonfire, as a symbol of the people's connection to one another.
A lot of the Samhain celebration had to do with honoring Celtic gods, and there's evidence that the Celts would dress as these deities as part of the festival. They may have actually gone door to door to collect food to offer to the gods. It is fairly clear that Samhain involved an offering of food to spirits. There may have been animal sacrifices, and some historians say the Celts even sacrificed people, but the evidence is not conclusive.
The Celts believed in fairies and other mischievous creatures, and the notion of Halloween trickery may have come from their reported activities on Samhain. There's also good reason to suppose that the Celtic New Year's Eve was something like our own New Year's Eve -- a time when people let go of their inhibitions, drank heavily and got into trouble. The trickery tradition may simply come from this spirit of revelry. We'll see how the Celts also influenced the Halloween tradition of carving pumpkins next.