These days, everybody knows what the Holy Grail was. It was the cup the Jesus used during the Last Supper, right? After all, that's what an Indiana Jones movie said it was, so it must be true.
Well, no. The first time that a "grail" shows up in the records is in the stories of Chrétien de Troyes, who wrote what are now considered the first "Arthurian" stories in the 1180s. In his Perceval, a story he never finished, young Perceval visits a mysterious castle where he sees a procession, a maiden carrying a "grail" and a boy carrying a bleeding lance. At this point it isn't called a "holy" grail, although the Christian symbolism of the bleeding lance seems undeniable.
(The chalice pictured above is from eleventh-century Spain and is not the holy grail.)
In Chrétien's story, it turns out that the grail is a platter, carrying the wafer of communion (so it is at least sort of holy). This wafer is all that the wounded Fisher King eats. Young Perceval in the story is amazed at the sight but doesn't say anything, though it later turns out that he should have asked what it was, and that his asking would have healed the Fisher King, who is actually his uncle.
Okay, this seems somewhat obscure. The fact that it is theoretically set in Britain, though Chrétien probably never left France, doesn't exactly clarify. Shortly thereafter, the German writer Wolfram von Eschenbach wrote his own version, and now the grail is a miraculous stone. Wolfram did finish his version, and his Parzival finally gets back to the grail castle, asks what is going on, heals the wounded king, and is reunited with his beloved wife.
Around this time the grail stories got drawn into Joseph of Arimathea stories. A British writer said that Joseph, who is in the Bible as providing a tomb for Jesus after the Crucifixion, had come to Britain toward the end of his life, bringing the cup of the Last Supper, and converted the island to Christianity.
This did not settle things on the Continent, where the "Quest of the Holy Grail" stories have it a rather undefined object that flies around healing people if they deserve it. The questers have adventures and repent of their sins until they are worthy to see the grail. Here the Fisher King's daughter (unnamed) is the woman with whom Lancelot accidentally had a hot affair, resulting in the birth of Galahad. (You had to be there.)
Some people have tried to connect the Holy Grail with some sort of ancient pagan Celtic stone, but the story is too confusing already without bringing in pagan details that all medieval grail authors would have rejected. (See more here on the historical (?) Arthur.)