We present the results of a pilot survey to find dust-reddened quasars by matching the FIRST radio catalog to the UKIDSS near-infrared survey, and using optical data from SDSS to select objects with very red colors. The deep K-band limit provided by UKIDSS allows for finding more heavily-reddened quasars at higher redshifts as compared with previous work using FIRST and 2MASS. We selected 87 candidates with K<=17.0 from the UKIDSS Large Area Survey (LAS) First Data Release (DR1) which covers 190 deg2. These candidates reach up to ~1.5 magnitudes below the 2MASS limit and obey the color criteria developed to identify dust-reddened quasars. We have obtained 61 spectroscopic observations in the optical and/or near-infrared as well as classifications in the literature and have identified 14 reddened quasars with E(B-V)>0.1, including three at z>2. We study the infrared properties of the sample using photometry from the WISE Observatory and find that infrared colors improve the efficiency of red quasar selection, removing many contaminants in an infrared-to-optical color-selected sample alone. The highest-redshift quasars (z > 2) are only moderately reddened, with E(B-V) ~ 0.2-0.3. We find that the surface density of red quasars rises sharply with faintness, comprising up to 17% of blue quasars at the same apparent K-band flux limit. We estimate that to reach more heavily reddened quasars (i.e., E(B-V) > 0.5) at z>2 and a depth of K=17 we would need to survey at least ~2.5 times more area.