An allegory is a story with (count 'em) two levels of meaning. First, there's the surface of the story. You know, the characters and plot and all that obvious stuff. Then there's the symbolic level, or the deeper meaning that all the jazz on the surface represents.
The symbolic meaning of an allegory can be political or religious, historical or philosophical. Allegories are kind of like massive metaphors, but they usually come in narrative form—that is, they're told through stories.
Want a few examples?
C.S. Lewis's The Lion, the Witch, and the Wardrobe is a famous religious allegory. The lion Aslan is a stand-in for Christ, and the character of Edmund, who betrays Aslan, is a Judas figure. And you thought it was just a kids' book.
George Orwell's novel Animal Farm, on the other hand, is a political allegory. Though set in a barnyard, the novel also tells the story of the rise of the Communist party in Russia between 1917 and 1943. Although on the surface the story may seem to be about a bunch of talking farm animals, the novel also has a secondary meaning that readers in the know will piece together. The characters and actions in the plot can be directly interpreted as a representation of political events in Russian history.
Other famous allegories include John Bunyan's Pilgrim's Progress and William Golding's The Lord of the Flies. Just to spice things up, Edmund Spenser's The Faerie Queene is an allegory that takes poetic form.