Prester John was the greatest Christian King who never lived. All through the Middle Ages there were persistent legends (sometimes backed up by apparent documentation) about this powerful priest-king in the East who was ready to bring his powerful armies to attack the Muslims in concert with the Western Crusaders. The experts who discussed these legends on In Our Time were Marianne O'Doherty (University of Southampton), Martin Palmer (Director of the International Consultancy on Religion, Education, and Culture) and Amanda Power (University of Sheffield).
They opened the programme with a bit of a discussion about the historical truths in which these legends might've been rooted. During the early Middle Ages there was a large Christian population in the Middle East and in India. There's evidence that Western Christians were in contact with them - for instance King Alfred (of England) sent some people to India. It's written about as if the journey wasn't anything particularly special - a long way, and a relatively rare event but perfectly doable. These Christians weren't from the same branch of Christianity as the Western Church, and the two Churches would've regarded each other as heretics. They are sometimes referred to as Nestorian Christians, but that is a bit of a derogatory term and it's politer to refer to them as the Church of the East or the Syrian Church. The schism between this Church and Western Christianity hinges round a theological point about the nature(s) of Christ. Western Christianity (or monophysitism) holds that Jesus's human nature was absorbed into his divinity and he had only one nature. However those who followed Nestorious believed that Jesus had two natures that were only loosely connected (this is called dyophysitism) - he was both divine and human and those were separate from each other. So there was a substantial Christian population in the East (probably larger than in the West), which dwindled after the rise of Islam - after which the legends of Prester John began to develop.
The first forms of the legend are known from the 12th Century AD. One of these is an account of a visit to the Pope in 1122 by an emissary from Prester John. It's not clear to modern scholars what, if anything, this is actually based on - if there was any visit from anyone that got garbled in the reporting or if someone just made it all up. The emissary purportedly says that he has come form Prester John's kingdom to the east, and that Prester John had been leading a force to aid the Christians at Jerusalem. However the army had been unable to cross a river on the way, and had been forced to turn back. The account of this emissary's visit gives details of the fabulous force that Prester John had available, and gave hope they would make another attempt to join the Crusaders.
Another early piece of "evidence" for Prester John was a letter that was purportedly sent from Prester John to the Byzantine Emperor in 1165, and subsequently translated into German and forwarded on to the Holy Roman Emperor. This letter goes into detail about what life is supposedly like in the land that Prester John rules. It's an earthly paradise, full of wondrous beasts. Everyone lives long and virtuous lives, and after death they don't rot and will return to life at the Day of Judgement. The kings are always called Prester John and combine the roles of secular and religious leaders in one person. The experts on the programme said that it's extremely likely that this letter was originally written in German - it doesn't read like translated Greek. There's also no obvious reason why the Byzantine Emperor would be forwarding his post on to the Germans! The most plausible explanation for the letter is that it's a piece of propaganda produced by the Holy Roman Emperor's court. At the time he and the Pope were embroiled in a power struggle, and a document that explained how perfect everything would be if the secular leader of a country was also the spiritual leader was rather useful for the Holy Roman Emperor.
It seems odd to us as modern people to think that these tales of an earthly paradise (of an incredible nature) were so easily believable, but the programme pointed out that during this era there was a large body of literature of tales of wondrous lands beyond the known world. This is the period where maps have areas labelled as where the Doghead people live, and where the people live who have their faces in their torsos. Around the 12th Century and onwards this begins to change, as more people travel and write more accurate travelogues. It's a slow change though - not all the early travelogues are written by people who've actually been where they claimed to be. For instance the author John Mandeville apparently travelled to Prester John's land and met him - but a lot of other things in Mandeville's book are made up, and most of the rest appears to've been copied from other books. There's no indication Mandeville actually went anywhere! He's not the only example of this from the time, either.
The rise of the Mongols changes the legends of Prester John a bit. There are some stories about Prester John being conquered, but other stories suggest that maybe he was never in Central Asia and his land is actually in India. Another blow to the believability of the legends is that travellers visit the Mongols from Europe, and whilst they meet Christians they don't meet or find any evidence of Prester John. (Nor do they find any wondrous beasts, or Dogheads etc.) They do try and make an alliance with the Mongols against the Muslims, but this doesn't interest the Mongols.
And later still as China becomes more well known to Europeans it becomes ever more implausible that Prester John and his kingdom could be anywhere in Asia. By the 14th Century AD the legend of Prester John has shifted to Africa, and Ethiopia is the new focal point. As an aside one of the experts (I forget which one) said that you could think of the 14th Century as "the century when Ethiopia discovered the West". Ethiopia had been Christian since the early AD period, and in the 14th Century they sent emissaries to the Pope and to some of the European kings. They seemed to fit in with some of the Prester John stories - in particular the "long lost Christian Kingdom" aspects of it. And they also seemed to fit other legends about the Queen of Sheba. But the legends still weren't true. Which apparently didn't stop European travellers from visiting Ethiopia and asking the rather bemused locals about Prester John.
They finished up the programme by talking about whether or not people actually believed the stories at the time. I think the overall conclusion was that mostly they probably didn't, it was just a good story or a useful one for propaganda purposes. However there were examples of people who did believe - for instance during the Crusades some commanders made strategic errors because they believed they were about to be joined by Prester John's army any time now.