They used to use alum, among other things, to set the dye, and alum became a huge and very lucrative industry, fought over by the likes of Venice and the Vatican. By the late medieval period most of the colors we know today (including pure black, which was one of the most expensive) were available, if you could afford them.

G