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.