Why are dragons a common association with the Middle Ages? Did medieval people really believe in their existence?

Yes. Depending on the region, medieval people might have certainly believed in dragons with a few caveats: the first is that monsters and wonderous things that might have happened in your own region only happened in the distant past, and the second is that wonderous things that might exist at the same time as you generally only occurred very far away. A characteristic of medieval understandings of the "marvelous" or "monstrous" was that the further you went away from the "center" of the world (ie. the Mediterranean), the more weird creatures, monstrous humans, odd plants and bizarre natural phenomena you were likely to encounter. This is the reason why marvelous things were more likely to be reported in places like the Orient, the far north or Ireland.

In Ireland itself, people seem to have believed in what we would call "dragons", but as I mentioned above, they were believed to have existed in the far past. They are actually quite important figures in medieval Irish toponymies (the naming of places) as many place-names and geographical features were believed to have originated from dragons that had been slain by a hero or saint (or even a pre-Christian god!), whose titanic corpses then transformed the landscape in some way.

Initially this kind of narrative appears to have begun in the pre-Christian (and consequently pre-historic) period. To begin with, the Irish, like most other Celtic speaking peoples, regarded watery places as liminal spaces between the cultured, human, physical world and the supernatural otherworld. They seem to have thought that reality was "thinner" around these places (among others; 'fairy circles' and ancient Barrows are other examples), and a human was more likely to encounter unearthly creatures, spirits or gods near them. It was for this reason that the pre-historic Irish would cast offerings of weapons, jewelry, instruments and maybe even human sacrifices into bogs, rivers, lakes and streams; if you wanted to sate or please a god, there was no better place to put your offering than the "portal" to the otherworld.

It's for these reasons that Irish "dragons" (it might be more accurate to call them serpents or wyrms) are nearly totally associated with lakes and rivers. The general narrative of the Irish dragon-slaying occurs in one of these areas, where the heroic champion slays the creature and either its body carves out natural features in its death-spasms, or its copious amount of blood dyes the water red. One such example can be found in the Metrical Dindshenchas (a list of poems explaining Irish placenames):

Three turns the serpent made; 10] it sought out the soldier to consume him; it would have wasted by its nature all the kine of the indolent hosts of ancient Erin. Therefore Diancecht slew it: there was rude reason for clean destroying it, 15] for preventing it for ever from wasting above every resort, from consuming utterly. Known to me is its grave where he cast it, a tomb without walls or roof-tree; its evil ashes,–no ornament to the region 20] found silent burial in noble Barrow.

The character Diancecht here is actually a pre-Christian god (his name literally means something like "god of battle"). This is a pretty good demonstration of how these sorts of narratives played out. Later on, they are Christianized and the pagan martial hero is replaced by the Christian spiritual champion; Irish saints replace gods and warriors as the premier dragon-slayers. Probably the most well-known of these narratives deals with Saint Patrick himself killing a massive serpent with his crozier in a lake, tinting the water red with its blood and therefore giving it the name "Loch Dearg" ("Red Lake"). Indeed, it's quite possible that the Loch Ness monster mythos originated in this ancient Irish belief in lake-dragons! One of the most oft-cited proofs of Nessie's existence by its believers comes from the hagiography of Saint Colum Cille, where a Pictish man refusing to hear the Irish saint preach God's word wades into the River Ness and is killed by a serpent, only for Colum Cille to revive the man with his crozier. Although it doesn't exactly follow the typology I laid out above, all the constituent elements are there but have been inverted, so that the "dragon" has actually become an agent of God's punishment!