The power spectrum of density fluctuations is a foundational source of cosmological information. Precision cosmological probes targeted primarily at investigations of dark energy require accurate theoretical determinations of the power spectrum in the nonlinear regime. To exploit the observational power of future cosmological surveys, accuracy demands on the theory are at the one percent level or better. Numerical simulations are currently the only way to produce sufficiently error-controlled predictions for the power spectrum. The very high computational cost of (precision) N-body simulations is a major obstacle to obtaining predictions in the nonlinear regime, while scanning over cosmological parameters. Near-future observations, however, are likely to provide a meaningful constraint only on constant dark energy equation of state wCDM cosmologies. In this paper we demonstrate that a limited set of only 37 cosmological models -- the Coyote Universe suite -- can be used to predict the nonlinear matter power spectrum at the required accuracy over a prior parameter range set by cosmic microwave background observations. This paper is the second in a series of three, with the final aim to provide a high-accuracy prediction scheme for the nonlinear matter power spectrum for wCDM cosmologies.