I've seen how Horween do this. It's literally two guys with wide brushes painting the stuff on. It goes through multiple coats to get the necessary depth of colour, but they can turn almost any hide a different colour from its base. I was shown one beautiful chestnut hide intended for a shoe that was butter yellow on the underside. I think the coating fastness is a chemically controlled thing.