It's true that a few jurisdictions, at certain times in the Middle Ages, had harsh laws making proven homosexuality a capital offence. But they were the exception, not the rule - it certainly wasn't the standard thing some people here are claiming. And for what it's worth, these stricter laws were generally introduced only later in the Middle Ages, not in the period of the early game. That's also the same time that harsh laws against heretics and witches were also being introduced: society was just generally more intolerant of deviance after the Black Death.
Example: in 1049 Pope Leo IX wrote a letter, Ad splendidum nitentis, setting out what he thought were the appropriate punishments for clergy caught committing homosexual acts. Those who could be proven to have had anal sex ('the complete act against nature') were to be punished by... being stripped of Holy Orders. Nothing else. Those who had non-penetrative gay sex, 'by the hands of others' or 'between the thighs' for example, were to be given suitable penance for their sin, such as fasting, then forgiven and allowed to remain as priests.
As for ordinary people, homosexual sex was certainly considered a sin, but in general no more sinful than adultery or masturbation. It was punished by the ecclesiastical courts in the same way as those other offences. (As mentioned, though, the Church generally became more condemning as time went on.)
A well-known case made famous by the historian Le Roy Ladurie was that of Arnaud de Verniolle, a young trainee priest who was arrested, imprisoned and interrogated by the French Inquisition in the 1320s. The Inquisition's records reveal that he had a vast and varied gay sex life in the small French town of Pamiers, seducing multiple partners ranging from priests and students to shoemakers. Many of the people he named were also questioned by the inquisitors, and confirmed his story (though some of them claimed they were coerced into the sex.)
Here's the thing, though - the Inquisition was actually much more worried by Arnaud's heretical religious views and the fact that he was hearing people's confessions despite not being an ordained priest. That was why he was arrested, and while his homosexuality was certainly a factor in the case, it was his heresy that eventually got him convicted. And no, he wasn't executed, for either crime - he was given life imprisonment. As for the other witnesses who confessed to having sex with him, I can't find what happened to them: but there's no evidence they were even punished. Nor did the Inquisition bother to investigate further into what was apparently a rampant gay scene in the town of Pamiers. As long as the people concerned weren't heretics, the Bishop in charge didn't really care.
Another famous mediaeval gay person (allegedly) was King Edward II of England. On one level, you could say that he got into trouble because of it: both his 'favourites', Piers Gaveston and Hugh Despenser, were brutally killed by rebellious barons, and later on so was Edward himself. However, the (alleged) gay sex only caused scandalous rumours; what really annoyed the barons was when Edward went on to heap his (alleged) lovers with titles and riches and privileges and power. The barons rebelled because they were jealous, not homophobic.
(And also, for the record, Edward had five children. He knew his dynastic duty.)