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.