Combining the public JWST/NIRCam imaging programs CEERS, PRIMER, and JADES, spanning a total area of $\sim 500\, {\rm arcmin}^2$, we obtain a sample of $\gt $30 000 galaxies at $z_{\rm phot}\sim 4\!-\!9$ that allows us to perform a complete, rest-optical-selected census of the galaxy population at $z\gt 3$. Comparing the stellar mass $M_*$ and the UV-slope $\beta$ distributions between JWST- and HST-selected samples, we generally find very good agreement and no significant biases. Nevertheless, JWST enables us to probe a new population of UV-red galaxies that was missing from previous HST-based Lyman-break galaxy (LBG) samples. We measure galaxy stellar mass functions (SMFs) at $z\sim 4\!-\!9$ down to limiting masses of $10^{7.5}\!-\!10^{8.5}\, {\rm M_\odot }$, finding steep low-mass slopes over the entire redshift range, reaching values of $\alpha \approx -2$ at $z\gtrsim 6$. At the high-mass end, UV-red galaxies dominate at least out to $z\sim 6$. The implied redshift evolution of the SMF suggests a rapid build-up of massive dust-obscured or quiescent galaxies from $z\sim 6$ to $z\sim 4$ as well as an enhanced efficiency of star formation towards earlier times ($z\gtrsim 6$). Finally, we show that the galaxy mass density grows by a factor $\sim 20\times$ from $z\sim 9$ to $z\sim 4$. Our results emphasize the importance of rest-frame optically selected samples in inferring accurate distributions of physical properties and studying the mass build-up of galaxies in the first 1.5 Gyr of cosmic history.