The magnitude-redshift relation for Type Ia supernovae is beginning to provide strong constraints on the cosmic densities contributed by matter, Omega(m), and a cosmological constant, Omega(Lambda), although the results are highly degenerate in the Omega(m)-Omega(Lambda) plane. Here we estimate the constraints that can be placed on a cosmological constant or quintessence-like component by extending supernovae samples to high redshift. Such measurements, when combined with constraints from anisotropies in the cosmic microwave background (CMB), could provide an important consistency check of systematic errors in the supernovae data. A large campaign of high-z supernovae observations with 10-m class telescopes could constrain Omega(m) to an accuracy (1 sigma) of 0.06 and Omega(Lambda) to 0.15. A sample of supernovae at redshift z similar to 3, as might be achievable with a Next Generation Space Telescope, could constrain Omega(m) to an accuracy of about 0.02 independently of the value of Omega(Lambda). The constraints on a more general equation of state, w(Q) = p/rho, converge slowly as the redshift of the supernovae data is increased. The most promising way of setting accurate constraints on w(Q) is by combining high-z supernovae and CMB measurements. With feasible measurements it should be possible to constrain w(Q) to a precision of about 0.06, if the Universe is assumed to be spatially flat. We use the recent supernovae sample of Perlmutter et al. and observations of the CMB anisotropies to constrain the equation of state in quintessence-like models via a likelihood analysis. The 2 sigma upper limits are w(Q)<-0.6 if the Universe is assumed to be spatially flat, and w(Q)<-0.4 for universes of arbitrary spatial curvature. The upper limit derived for a spatially flat Universe is close to the lower limit (w(Q)approximate to-0.7) allowed for simple potentials, implying that additional fine tuning may be required to construct a viable quintessence model.