Actually... I like the idea of hair dye being an item. You could go to a salon to get it styled a certain way and then you could dye it depending on which dye bottles you have.
The plants on the overworld thing would be neat. It would add some random aesthetics to the OW and people could get lucky and find the "rarer" colors... Though I think the normal colors could be available in shops or something.
Going by what was said above... I think it would work to have players find these colored plants and pick them. Then take them to a place where they drop it in a barrel and add some water, and then stir it using the directional keys (like going up left down right around and around) and then if they have a bottle they can put the dye in the bottle.
I don't really think it would work too well for clothing... since hair isn't an item it works easier. But yeah, I like the hair dye idea... I might do something like that. There would still be a lot of colors you could change your hair to without finding the dye.