We present host stellar velocity dispersion measurements for a sample of 88 broad-line quasars at 0.1<z<1 (46 at z>0.6) from the Sloan Digital Sky Survey Reverberation Mapping (SDSS-RM) project. High signal-to-noise ratio coadded spectra (average S/N~30 per 69 km/s pixel) from SDSS-RM allowed decomposition of the host and quasar spectra, and measurement of the host stellar velocity dispersions and black hole (BH) masses using the single-epoch (SE) virial method. The large sample size and dynamic range in luminosity (L5100=10^(43.2-44.7) erg/s) lead to the first clear detection of a correlation between SE virial BH mass and host stellar velocity dispersion far beyond the local universe. However, the observed correlation is significantly flatter than the local relation, suggesting that there are selection biases in high-z luminosity-threshold quasar samples for such studies. Our uniform sample and analysis enable an investigation of the redshift evolution of the M-sigma relation free of caveats by comparing different samples/analyses at disjoint redshifts. We do not observe evolution of the M-sigma relation in our sample, up to z~1, but there is an indication that the relation flattens towards higher redshifts. Coupled with the increasing threshold luminosity with redshift in our sample, this again suggests certain selection biases are at work, and simple simulations demonstrate that a constant M-sigma relation is favored to z~1. Our results highlight the scientific potential of deep coadded spectroscopy from quasar monitoring programs, and offer a new path to probe the co-evolution of BHs and galaxies at earlier times.