They will reach the correct theory eventually, because all the theories would be fairly easy for them to test.
Lets take a simple scenario. There is a farmer, who works in a field. Every day, for 16 hours a day. He tends the ground, carries crops, and takes it to market to sell. Now he is fairly strong. He does this all by himself. This makes the Noble who he sells to wonder why is it that a farmer is stronger than him. He comes up with several theories
- He was born that way
- Its because of what he eats
- Divine blessings
- Its because of what he does
In an effort to also become strong, the Noble investigates. Firstly, he notices that there are a lot of other farmers. So many being Born a farmer makes you stronger. The Noble however, also notices that the Knights from royal families seem pretty strong. So do the blacksmiths, wood workers, fishers and some other professions. Since its such a wide range of people, he knows it wasn't being born that way.
Then the noble looks at his second option. Is it what he eats? The noble, being able to afford the same food, sets out on a diet that matches the farmer. After a couple of weeks, he feels no difference. In fact he feels even weaker than he was before. So he rules that out.
Next the Noble is convinced that its because of the divine blessings. He visits the local church to which he is a generous donator of, to receive the blessing. But lo and behold, all the priests and nuns are such as weak as he is. While the priest does bless him, the noble quickly realizes that he is just as weak as he was before the blessing.
So finally, he asks himself, Maybe its what the farmer does everyday. Not very happy with the prospect of hard labor, the Noble simply decides to carry some more equipment around during his day to day activities. After a couple weeks, he realises he is strong and that the equipment he was carrying before feels a bit lighter. He isn't completely out of breath, but he is still tired. He tries to lift some heavier things and after another couple of weeks realises that it too has also become easier to lift.
The happy noble, stops excising and arranges for a feast where he will spread the good news. Over the coming weeks, he doesn't do any exercise because he is too busy preparing the party. On the Night of the party, he gets his butler to bring out the weight and tries to lift it again. After much boasting and applause, he fails, after much embarrassment, he retires to his chambers early.
The other nobles, head off home and gossip about it. They come up with their own theories
- Is it true you can get strong by lifting heavy things?
- Will I always stay that strong?
- Do I have to keep lifting heavy things to stay strong after I become strong
- How much can I lift before I stop becoming stronger
The only interesting catch would be due to intensive exercise. "If you exercise too hard, it makes you weaker" but in the long run, they would figure out how to get stronger. Its easy to look at someone strong and isolate what they did to make themselves strong.
Edit: A note about the invisible germs
There are many invisible germs that cause many different problems. Peoples bodies also react differently and it is influenced by a ton of factors like your parents, who you are in contact with, hygiene and diet. Two people can catch the same disease and have widely different reactions. With so much variety, its very hard to narrow down whats the individual cause. With exercise, there is basically only one thing that happens. You get stronger/fitter over time. It doesn't really matter who the person is, who they hang out with, who they were born as, who they worship, what their body is like. As long as they perform an exercise over and over again, it becomes easier. That's not to say it becomes trivial to perform, its just easier than someone who doesn't perform the same exercise.