Distant star-forming galaxies show a correlation between their star formation rates (SFR) and stellar masses, and this has deep implications for galaxy formation. Here, we present a study on the evolution of the slope and scatter of the SFR-stellar mass relation for galaxies at $3.5leq zleq 6.5$ using multi-wavelength photometry in GOODS-S from the Cosmic Assembly Near-infrared Deep Extragalactic Legacy Survey (CANDELS) and Spitzer Extended Deep Survey. We describe an updated, Bayesian spectral-energy distribution fitting method that incorporates effects of nebular line emission, star formation histories that are constant or rising with time, and different dust attenuation prescriptions (starburst and Small Magellanic Cloud). From $z$=6.5 to $z$=3.5 star-forming galaxies in CANDELS follow a nearly unevolving correlation between stellar mass and SFR that follows SFR $sim$ $M_star^a$ with $a = 0.54 pm 0.16$ at $zsim 6$ and $0.70 pm 0.21$ at $zsim 4$. This evolution requires a star formation history that increases with decreasing redshift (on average, the SFRs of individual galaxies rise with time). The observed scatter in the SFR-stellar mass relation is tight, $sigma(log mathrm{SFR}/mathrm{M}_odot$ yr$^{-1})< 0.3 - $ 0.4 dex, for galaxies with $log M_star/mathrm{M}_odot > 9$ dex. Assuming that the SFR is tied to the net gas inflow rate (SFR $sim$ $dot{M}_mathrm{gas}$), then the scatter in the gas inflow rate is also smaller than 0.3$-$0.4 dex for star-forming galaxies in these stellar mass and redshift ranges, at least when averaged over the timescale of star formation. We further show that the implied star formation history of objects selected on the basis of their co-moving number densities is consistent with the evolution in the SFR-stellar mass relation.