Did they even have a theory as to what was happening? How were they able how to do the correct things like maintain cultures for cheese or yogurt making, and perfect processes like beer making, if they didn't actually know what was happening?
I'm not a historian but I'm a home brewer, if I cite sources hopefully I won't be deleted (apologies, this is my first post here).
Yeast is naturally in your environment, you don't need to maintain cultures for it to "work" it's already here http://en.wikipedia.org/wiki/Yeast . The word origins on Yeast derive from froth/boil (http://www.etymonline.com/index.php?term=yeast) so it was describing the observed action of fermentation even if the mechanism wasn't fully understood. Again, people certainly observed the action of yeast even if they didn't understand microorganisms.
Sandor Katz has a fantastic book called "Wild Fermentation" that outlines, at length, how to create many things such as bread, beer, etc using natural yeast from your local environment. All of these work without "starters" you just leave things out in a certain way and it ferments. The primary difference between your local yeast and buying yeast is local yeast varies a lot more in flavor and with an open air ferment you can get a ton of other less tasty bacteria introduced as well that makes things taste sour especially lactobacillus (http://en.wikipedia.org/wiki/Lactobacillus) which is important to the yogurt/etc that you mention.
It's paywalled, but this article "Bread and beer in fourthâmillennium Egypt" outlines a recipe for bouza, a 5000 year old Egyptian beer recipe. http://www.tandfonline.com/doi/abs/10.1080/07409710.1993.9962007#.VD1LQtR4pmQ So it's quite clear that recipes for beer that require the action of yeast have been well known for a very very long time.
As far as refining it and learning to cultivate a yeast starter, I have no source but I assume it happened by trial/error. Someone added some of their live bread batter to their next loaf and noticed it turned out better, so they kept doing it.
Finally, there's no primary source but it's a story I'd love to believe via John Palmer in his book "How to Brew":
"In the days of the Vikings, each family had its own brewing stick, which was used for stirring the wort. These brewing sticks were family heirlooms, because it was the use of the stick that guaranteed that the beer would turn out right. Obviously, those sticks retained the family yeast culture."
Sorry I don't have a primary on that :/
Not a historian, but are you sure they didn't know what yeast was? In the Bible, yeast (or leaven) is mentioned quite frequently. Thus, Manna is a traditional Jewish bread (bread without yeast) because traditionally, the Israelites did not have time to let their dough rise before the exodus from Egypt.
The concept of Spontaneous Generation may have had a part in this. It was a commonly held belief that things could just change if the conditions were correct. The leavening of bread would have been no more mysterious than any other "invisible" process.