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