We study the clustering properties of K-selected galaxies at 2<z<3.5 using deep multiwavelength imaging in three fields from the MUSYC survey. These are the first measurements to probe the spatial correlation function of K-selected galaxies in this redshift range on large scales, allowing for robust conclusions about the dark matter halos that host these galaxies. K-selected galaxies with K<21 have a correlation length r_0 ~ 6 h^-1 Mpc, larger than typical values found for optically-selected galaxies. The correlation length does not depend on K-band magnitude, but it does increase strongly with color; the J-K>2.3 distant red galaxies (DRGs) have r_0 ~ 11 h^-1 Mpc. Contrary to findings for optically-selected galaxies, K-selected galaxies that are faint in the R-band cluster more strongly than brighter galaxies. These results suggest that a color-density relation was in place at z>2. Our results indicate that K-bright blue galaxies and K-bright red galaxies are fundamentally different, as they have different clustering properties. Using a simple model of one galaxy per halo, we infer halo masses ~ 5 x 10^12 M_sun for K<21 galaxies and ~ 2 x 10^13 M_sun for DRGs. A comparison of the observed space density of DRGs to the density of their host halos suggests large halo occupation numbers; however, this result is at odds with the lack of a strong small-scale excess in the angular correlation function. We find that the z=0 descendants of the galaxies considered here reside primarily in groups and clusters. [abridged]