We develop a general operational framework that formalizes the concept of conditional uncertainty in a measure-independent fashion. The formalism is built around a mathematical relation that we call conditional majorization. We define and characterize conditional majorization, and use it to develop tools for the construction of measures of the conditional uncertainty of individual measurements, and also of the joint conditional uncertainty of sets of measurements.