I am in no way able to discuss the entirety of Europe, but I can address a few areas during the high Middle Ages (1000-1300), as per your PM - though to be honest, there is not very much to say about this period when it comes to fashion, either for the head or the body. The concept of being in fashion did not really exist: instead of wearing the colors deemed to be "in" or clothing cut in the new way, one displayed status by wearing colors made from expensive dyes and clothing cut from lavish amounts of fabric. Without the need to continually adopt new forms to show status, change in hairstyles and clothing styles occurred slowly.

In Norman England and on the continent, men's hair tended to be worn short - ranging from jaw/chin-length to just above shoulder-length, with the shorter styles generally earlier in the period and longer later; the hairline might be uncovered, or trimmed with short, curled bangs. It's difficult to say what is stylization in art and what is a representation of deliberate hair styling, but men's hair in illustration generally looks somewhat wavy or curly, or is only curled at the ends. Men of lower status usually covered their hair with white coifs, close-fitting caps of very simple construction (made with only one or two seams, a plain hem around the edges, and strings attached which tied under the chin to hold the cap on tightly. Middle and upper class men more frequently wore (alone or over the coif) hats with short crowns and vertical sides/turned-up brims. Woolen hoods, generally attached to cowls of varying lengths, were also common accessories.

Meanwhile, women's hair was longer; just as it's hard to tell what is stylization and what is styling in men's hair, women's generally appears to be in tight waves or curls when it's down, as it could be for young, unmarried women. Married women more frequently wore it up, fastened low at the back of the head. Coifs could be worn over up or down hair, and alone or with a second headdress - during this period, the second headdress was usually a veil, especially for married/adult women. Another headdress, more common toward the end of the period, was a fillet (a circlet around the head with some height to it) and barbette (a strip of fabric running over the top of the head and under the jaw, usually under the fillet), which could be worn with or without a coif beneath or veil on top. (Here's a blog post with several images of them with slightly different styling.)