To answer the "when" question, the exact date is unknown (patron saint assignments were not decided by official decree, but rather were adopted by people over time), but the association dates back to at least the Middle Ages.
As alluded to by previous answers, there are two theories on "why" question.
Theory 1: anointing Jesus' feet
The first is that the association derives from the Gospel of Luke. Pope Gregory (reigned 590-604) popularized the idea that three women described in the Gospels - Mary Magdalene (Matthew 27:56, 61; 28:1; Mark 15:40, 47; 16:1-19; Luke 8:2; 24:10; John 19:25; 20:1-18), Mary, the sister of Martha and Lazarus (Luke 10:38-42), and the unnamed woman who anointed Jesus' feet (Luke 7:36-50) - were all the same person. (Later the story of the adulteress saved from stoning by Jesus [John 7:53-8:11] also came to be associated with Mary Magdalene.)
Because of this association, Mary was usually depicted as having long hair in medieval art. Naturally, a woman always depicted with long, flowing hair is a good choice for hairdressers to adopt as a patron saint.
A 14th century depiction of Mary Magdalene at the cross of Jesus
A medieval legend reinforces the idea that her hair had become to be seen as her key trait. In the legend, Mary, Martha, and Lazarus bring the Gospel to France. After spreading the Gospel, Mary retires to a cave to pursue a contemplative, solitary life. Over time, her clothes wear out but miraculous her hair grows to cover her entire body, preserving her modesty.
Mary, covered in hair, being lifted up by angels
Theory 2: actual hairdresser
An alternate theory is that Mary Magdelene's actual profession was that of a hairdresser, or at least that she was associated with the profession from a very early date. There are two references in the Talmud to a Miriam megaddelah nashaia (Mary, the plaiter of women’s hair). While it is debated whether this Miriam (Mary) is actually the same person as Mary Magdelene, it does raise the interesting possibility that "Magdelena" does not refer to a place name, Magdala, as traditionally thought, but rather a profession, megaddelah. Since surnames weren't in use yet in the first century, people were often given nicknames to distinguish them from others with the same name. Such nicknames could refer to a place of origin, but could also refer to a profession (among other things), so the theory is at least plausible.
Certainly it would a funny coincidence if Mary's nickname just happened to resemble a word she later came associated with for completely unrelated reasons.