We report results from a Giant Metrewave Radio Telescope search for associated redshifted HI 21cm absorption from 24 active galactic nuclei (AGNs), at $1.1 < z < 3.6$, selected from the Caltech-Jodrell Bank Flat-spectrum (CJF) sample. 22 out of 23 sources with usable data showed no evidence of absorption, with typical $3sigma$ optical depth detection limits of $approx 0.01$ at a velocity resolution of $approx 30$~km~s$^{-1}$. A single tentative absorption detection was obtained at $z approx 3.530$ towards TXS0604+728. If confirmed, this would be the highest redshift at which HI 21cm absorption has ever been detected. Including 29 CJF sources with searches for redshifted HI 21cm absorption in the literature, mostly at $z < 1$, we construct a sample of 52 uniformly-selected flat-spectrum sources. A Peto-Prentice two-sample test for censored data finds (at $approx 3sigma$ significance) that the strength of HI 21cm absorption is weaker in the high-$z$ sample than in the low-$z$ sample, this is the first statistically significant evidence for redshift evolution in the strength of HI 21cm absorption in a uniformly selected AGN sample. However, the two-sample test also finds that the HI 21cm absorption strength is higher in AGNs with low ultraviolet or radio luminosities, at $approx 3.4 sigma$ significance. The fact that the higher-luminosity AGNs of the sample typically lie at high redshifts implies that it is currently not possible to break the degeneracy between AGN luminosity and redshift evolution as the primary cause of the low HI 21cm opacities in high-redshift, high-luminosity active galactic nuclei.