Motivated by recent experimental work on multicomponent lipid membranes supported by colloidal scaffolds, we report an exhaustive theoretical investigation of the equilibrium configurations of binary mixtures on curved substrates. Starting from the Julicher-Lipowsky generalization of the Canham-Helfrich free energy to multicomponent membranes, we derive a number of exact relations governing the structure of an interface separating two lipid phases on arbitrarily shaped substrates and its stability. We then restrict our analysis to four classes of surfaces of both applied and conceptual interest: the sphere, axisymmetric surfaces, minimal surfaces and developable surfaces. For each class we investigate how the structure of the geometry and topology of the interface is affected by the shape of the substrate and we make various testable predictions. Our work sheds light on the subtle interaction mechanism between membrane shape and its chemical composition and provides a solid framework for interpreting results from experiments on supported lipid bilayers.