  The Canada-France High-z Quasar Survey (CFHQS) is an optical survey designed
to locate quasars during the epoch of reionization. In this paper we present
the discovery of the first four CFHQS quasars at redshift greater than 6,
including the most distant known quasar, CFHQS J2329-0301 at z=6.43. We
describe the observational method used to identify the quasars and present
optical, infrared, and millimeter photometry and optical and near-infrared
spectroscopy. We investigate the dust properties of these quasars finding an
unusual dust extinction curve for one quasar and a high far-infrared luminosity
due to dust emission for another. The mean millimeter continuum flux for CFHQS
quasars is substantially lower than that for SDSS quasars at the same redshift,
likely due to a correlation with quasar UV luminosity. For two quasars with
sufficiently high signal-to-noise optical spectra, we use the spectra to
investigate the ionization state of hydrogen at z>5. For CFHQS J1509-1749 at
z=6.12, we find significant evolution (beyond a simple extrapolation of lower
redshift data) in the Gunn-Peterson optical depth at z>5.4. The line-of-sight
to this quasar has one of the highest known optical depths at z~5.8. An
analysis of the sizes of the highly-ionized near-zones in the spectra of two
quasars at z=6.12 and z=6.43 suggest the IGM surrounding these quasars was
substantially ionized before these quasars turned on. Together, these
observations point towards an extended reionization process, but we caution
that cosmic variance is still a major limitation in z>6 quasar observations.
