Today, nearly all commercial footwear has a sole made of either rubber or plastic with rubber-like qualities. It's a great material for the job, but it comes from a tree that's native to the Americas, and thus was unavailable to the Old World before Columbus.
What did they make shoe and boot soles out of in earlier ages? Ideally, it would have to be something relatively tough, firm and resistant to wear, in contrast to the rest of the shoe which should ideally be relatively soft and flexible.
Leather was probably the most common material.
The most basic transportation technology of the medieval era was the foot ... Those who did not go barefoot ... wore simple shoes. These shoes were made from leather, including the flat sole.
- Wigelsworth, Jeffrey R. Science and Technology in Medieval European Life. Greenwood Publishing Group, 2006.
Medieval shoes in general were typically made of leather, and for the simplest designs it was little more than a piece of leather strapped on to the ankle with drawstrings or some similar mechanism.
For footwear, men and women both wore similar styles of leather shoes and low boots; the latter were particularly favored by working folk. The dominant style of the twelfth century relied on drawstring thongs laced around the ankle to keep the shoe on the foot; surviving thirteenth-century shoes are sometimes fastened with lacings up the inner side or with toggles. The sole was flat with no additional heel. As the sole wore out, it might be patched with another piece of leather.
- Forgeng, Jeffrey L., and Jeffrey L. Singman. Daily life in Medieval Europe. Greenwood Publishing Group, 1999.
One popular method of manufacturing shoes led to what is called turnshoes, so named because it was sewn inside out, then turned upright when finished. These used only a layer of leather and while primitive, remained in use for a long time.
The type of shoe made throughout medieval Europe was that known as the 'turnshoe' in which the upper, often of supple goatskin, was sewn onto the sole, normally of cow-hide, and then the whole turned inside out so that the sewn seam was concealed.
- Clarke, Helen. The Archaeology of Medieval England. British Museum Publications, 1984.
In addition, some shoes were made with wooden soles, which allowed for footwear with hard soles (turnshoes could only be made with soft ones). This mainly took the form of pattens, and were effectively wooden slippers.
[A]t least a few pattens were made with thin, flat wooden soles supported on iron braces instead of wooden arches ... Interestingly, pattens seem to have been the only wooden footwear in the Middle Ages. Clogs with wooden soles and leather uppers and shoes made entirely of wood such as those traditionally associated with Holland do not appear to have come into common use until some time after the Middle Ages.
- Newman, Paul B. Daily life in the Middle Ages. McFarland, 2001.
One kind of shoe not mentioned in the other answers are those using bast soles. "Bast" is fiber from tree bark. Bast shoes or lapti, were once worn by poorer members of Northern European cultures. These were usually made from birch or linden. They are woven like a basket, and so are quite distinct from the wooden clog or hard wooden-soled shoes mentioned in the other answers.
In Spain (especially Catalonia) and France (especially Occitania), espadrilles, soled with jute rope, have been worn since at least the 14th century. Jute is also a bast fiber. Unlike the woven bast shoes of Northern Europe, espadrilles generally only make use of jute in the soles.
Thanks to @MartinArgerami for mentioning espadrilles.
In Europe, different demands were placed on shoes based on different climates.
Of course, you can compare this with footwear in other parts of the world, like the moccasins of America or the sandals of eastern Asia. Fashion also comes into play, like the shoes of royalty or a jester.
As others have mentioned, leather has been to preferred choice of material for the soles of footwear for thousands of years. An interesting fact is that one of the technologies that gave the Romans such an advantage was their hardened leather sandals which allowed them to march 20 miles a day, every day. Untreated leather and animal skins would wear out after three or four days at that pace slowing an enemy army down and giving the Romans an advantage. The technology to harden leather was lost with the fall of the Roman empire and does not appear to have been recovered until the late medieval period.
Leather for sure. My boots are all leather except for a piece of rubber at the bottom of the heel. "Tough, firm, resistant to wear" exactly describes traditional leather use. The soles and any other parts are replaced as needed; my "cheap" boots as a teen lasted 10 years, and my current Ostrich ropers are 15 years old and "like new". Nylon/rubber/synthetic shoes last less than a year of use.
Leather was "perfected" in ancient times, and can be manufactured with variable properties to suit the specific part. Different leathers and other material are laminated to form what we call composites today, but ancient people already mastered that concept.
It's also important that the boot can be disassembled, using reversable hide glue, nails, and stiching, so individual components can be repaired and replaced. My brand-new 15-year-old boots were torn down and rebuilt on the original last (wood form).
