We conducted an exploratory search for quasars at z similar to 6-8, using the Early Data Release (EDR) from the United Kingdom Infrared Deep Sky Survey (UKIDSS) cross-matched to panoramic optical imagery. High-redshift quasar candidates are chosen using multi-color selection in i, z, Y, J, H, and K bands. After removal of apparent instrumental artifacts, our candidate list consisted of 34 objects. We further refined this list with deeper imaging in the optical for ten of our candidates. Twenty-five candidates were followed up spectroscopically in the near-infrared and in the optical. We confirmed 25 of our spectra as very low-mass main-sequence stars or brown dwarfs, which were indeed expected as the main contaminants of this exploratory search. The lack of quasar detection is not surprising: the estimated probability of finding a single z > 6 quasar down to the limit of UKIDSS in 27.3 deg(2) of the EDR is < 5%. We find that the most important limiting factor in this work is the depth of the available optical data. Experience gained in this pilot project can help refine high-redshift quasar selection criteria for subsequent UKIDSS data releases.