What could be found underground that would provide fibres that could be turned into textile? The source of the fibres should be found buried in soil, in temperate regions. It also should be something that could have evolved (or otherwise come to be) on Earth. Preferably, it would also be possible to breed this source with technology similar to medieval Europe
There's a lot of options here but it sounds like you wants something farmable. Here's a few that I found around the internet and while some would need you to stretch your imagination others wouldn't.
Fermented Wine Joe is a farmer who many considered mad but when he started burying red wine under the ground many people started avoiding him. Some of the kids who still visited Joe told fantastical stories about Joe turning wine into clothing of all things but kids you know? Turns out they weren't wrong.
Turns out Joe had figured out how to use some fancy bacteria, not that the towns folk know what that is, in the genus Acetobacter to make vinegar. On the plus side a side product is fibers that can be turned into cloth. While quite strange it is feasible with medieval european technology and even likely to bury under the wine under the ground to keep it at a relatively consistent temperature long enough for the bacteria to do it's thing. Vinegar was also useful for other things. As for why Joe decided he'd rather bury his red wine instead of do stuff with it? Maybe the price fell. Maybe he was being pressured to sell it and decided to make vinegar instead.
As for how Joe realized he could make fabric out of the wine or even that there was weird stuff, Acetobacter requires oxygen to work best and since Joe was trying for vinegar that would work best. As for why vinegar? Maybe he's mad. Either way he got some wierd fabric out of it at least.
Spider Silk This one will require hand waving and either really weird spiders or giant spiders. Either way we have giant spider eggs sacks that are buried under the ground like turtles for the spiders to burst forth and do spider things. Then we have Maria, who say lives near the woods, and decides to pull a chinese silk farming method (Idk why or how maybe she has spies that told her about silk worms.) and she killed off the baby spiders and used the silk for spider silk. I'm not certain but it's a possibility of digging up spider silk and weaving it.
Plant roots? This one would require more hand waving in my opinion but I don't see why it wouldn't be possible to get textiles out of it. More likely it would be some type of novelty lace that would fade away quickly though.
Sarah the nun was tending to the gardens when she thought to herself, 'You know I bet if I made the soil in weird shapes I could get the roots to make pretty patterns.' https://www.designboom.com/art/diana-scherer-manipulated-plant-roots-patterns-01-21-2017/
This took her a long time, and depending on the level of communication people have and how likely they are to listen to Sarah the low level gardener might increase the field of agriculture, but she could make some pretty patterns and probably sell them about. Maybe even teach a few people how to do it and make it the latest trend. If you hand wave it then the roots could theoretically become short term clothing.
Strange breeds Most aren't aware the bees make silk but they do in order to make their hives. Do some hand waving and you could say that some wild bees made collectable silk that could be turned into fabric with a little bit of work. Include a few bee caves and wabam.
You could also make upside down cotton, or some such thing, that grows a pod underneath the ground to keep it safe until a human comes along to dig it up and gather it. There's a bunch of different options but these are some that I gathered.
King, I feel obliged to point out that the bright white suit you are wearing is pure polyester made from petrochemicals that were found underground in a temperate climate. Those nylon baggies with the rocket ships that you wear as underwear were also made from petrochemicals found underground. But maybe the medievals could not make polyester.
Instead I will reuse this old answer:
... because the ancient Romans were said to have woven asbestos fibers into a cloth-like material that was then sewn into tablecloths and napkins. These cloths were purportedly cleaned by throwing them into a blistering fire, from which they came out miraculously unharmed and essentially whiter than when they went in. While Greeks and Romans exploited the unique properties of asbestos, they also documented its harmful effects on those who mined the silken material from ancient stone quarries. Greek geographer Strabo noted a “sickness of the lungs” in slaves who wove asbestos into cloth... Around 755, King Charlemagne of France had a tablecloth made of asbestos to prevent it from burning during the accidental fires that frequently occurred during feasts and celebrations. Like the ancient Greeks, he also wrapped the bodies of his dead generals in asbestos shrouds. By the end of the first millennium, cremation cloths, mats and wicks for temple lamps were fashioned from chrysotile asbestos from Cyprus and tremolite asbestos from northern Italy.
Asbestos is mined. It is fibers and it can be made into cloth. Charlemagne's crew could do it and so can your medievals. Yes, yes, cancer, lung disease etc. We can say your people are unworried about risk - they wear asbestos bikini briefs, refuse the covid shot and smoke filterless Lucky Strikes while jaywalking.
I spin yarn, so I have some experience with this subject, or at least with the articles on this subject. One of the most common ways to spin fibers from plants is to ret them (controlled rotting that removes the unspinnable portions and softens the phloem into bast fibers), comb them (on a hackle or other combs), then spin them “wet” (using water or spit on the fingers as you draft).
Most notably, this is done with flax to make linen, but it is usable with the stems of nearly every plant. There isn’t anything I could find that would definitely confirm or deny that this would work with the roots of any plants, so I wouldn’t try this with plant roots. However, if you have a plant with stems underground, you could use those.
The hard part here will be finding a plant that grows underground and has a stem to ret. I’d try any plant with stolons first, which are probably spinnable, though I haven’t tested it.
To ret fibers, by the way, requires a source of stagnant water, in which you immerse the whole plants you’re working with. Then you leave it for a while, and let them rot. Around 2-3 weeks later (source, which also provides a decent overview of the process), they should be good to go. This will of course vary based on location and weather and the plants you’re using, but it’s an estimate. Then, you heckle or hackle the fibers to separate the leftover stuff from the bast (you ought to rinse it first, though), and finally you can spin it.
Another source of information on bast fibers, although less comprehensive, is Clara Parkes’ book The Knitter’s Guide to Yarn, which is a decent overview of the general process of fiber-processing and covers the details of how, precisely, these fibers feel when used.