State estimator design for a nonlinear discrete-time system is a challenging problem, further complicated when additional physical insight is available in the form of inequality constraints on the slate variables and disturbances. One strategy for constrained state estimation is to employ online optimization using a moving horizon approximation. In this article we propose a general theory for constrained moving horizon estimation. Sufficient conditions for asymptotic and bounded stability are established. We apply these results to develop a practical algorithm for constrained linear and nonlinear state estimation. Examples are used to illustrate the benefits of constrained state estimation. Our framework is deterministic.