How are new staining protocols designed for microscopy?
This answer addresses the question of how stains were developed historically, which may bring into perspective your overly modern assumptions. 

Most of these older (but stil very usefull!) staining techniques, such as haematoxylin (or rather haematein), cochenial/carmine etc. were inspired by the work of textile dyers of that era, starting somewhere in the middle of the 19th century. 

It was more a question of trial and error, coïncidence and luck, rather than it being a case of systematic, structured research, starting from the well known molecular structure of the dye and the sample to be stained... Most of the time those were still -at least partial- mysteries. 

You should keep in mind, that many of the protocols still in use, were developed in an era when the dye industry as well was still in its infancy, so to speak. Standardization of dyes, Biological Stain Commission and all that, came later. Biologists, histologists etc. used what worked for them. At that time, at that place, with that lot of dry dye powder. Much inspiration, the right idea at the right time and a fair amount of luck. Up to well into the 20th century. 

As an illustration: in 1917-1918 there was a shortage on haematoxylin in the German histopathological labs, due to the allied blockade. A lab worker, Fraulein Wilhelmina Schmidt, inspired by the impossibillity to remove elderberry stains from her hands, wondered if it would be possible to use elderbery juice as a substitute for haematoxylin. As there wasn't really an alternative, it was tried. Elderbery juice was concentrated by boiling, diluted with an alum solution and tried. It turned out to work very well. 

The story went unnoticed until 1949, when an article on it was published in the German “Zeitschrift für die Wissenshaftliche Mikroskopie”. In the article, the author, Grüber, pointed out that, even after more than 20 years of storage, the slides were still vividly stained, not showing any trace of fading.