We use the UKIDSS Ultra-Deep Survey to trace the evolution of galaxy clustering to z = 3. Using photometric redshifts derived from data covering the wavelength range 0.3 - 4.5 um we examine this clustering as a function of absolute K-band luminosity, colour and star-formation rate. Comparing the deprojected clustering amplitudes, we find that red galaxies are more strongly clustered than blue galaxies out to at least z = 1.5, irrespective of rest-frame K-band luminosity. We then construct passive and star-forming samples based on stellar age, colour and star-formation histories calculated from the best fitting templates. The clustering strength of star-forming galaxies declines steadily from r_0 ~ 7 h^-1 Mpc at z ~ 2 to r_0 ~ 3 h^-1 Mpc at z ~ 0, while passive galaxies have clustering strengths up to a factor of two higher. Within the passive and star-forming subsamples, however, we find very little dependence of galaxy clustering on K-band luminosity. Galaxy `passivity appears to be the strongest indicator of clustering strength. We compare these clustering measurements with those predicted for dark matter halos and conclude that passive galaxies typically reside in halos of mass M > 10^13 M_sun while luminous star-forming galaxies occupy halos an order of magnitude less massive over the range 0.5 < z < 1.5. The decline in the clustering strength of star-forming galaxies with decreasing redshift indicates a decline in the hosting halo mass for galaxies of a given luminosity. We find evidence for convergence of clustering in star-forming and passive galaxies around z ~ 2, which is consistent with this being the epoch at which the red sequence of galaxies becomes distinct.