Pick your color, if it can dye wool it will dye hair just fine.
Here is a great photo showing a list of known natural dyes, all are possible with medieval technology. several were not available in the real medieval era because they come from the Americas. You can also have things link indigo, henna, and saffron for blue, reds, and orange respectively. Keep in mind as hair grow they will have to re-dye periodically. And of course bleaching your hair was a well known technique at the time.
Purity and boldness of color will be affected by cost of course, these would represent the more expensive dyes. keep in mind a commoner probably cannot afford expensive dye so they would be limited to reds and browns, nothing unnatural. These would be Henna (red/brown), Madder(red), onionskins (yellow), akderbark (orange), walnut (brown)
Although they may be able to achieve green with lichen, which is probably the only unnatural color they can achieve cheaply.
These are also the ones that are not downright toxic, using lead or lye were common at the time but were also toxic.