In this first of a two-paper sequence, we report techniques and results of the Cornell High-Order Adaptive Optics Survey ( CHAOS) for brown dwarf companions. At the time of this writing, this study represents the most sensitive published population survey of brown dwarf companions to main-sequence stars for separations akin to our own outer solar system. The survey, conducted using the Palomar 200 inch ( 5 m) Hale Telescope, consists of K-s coronagraphic observations of 80 main-sequence stars out to 22 pc. At 100 separation from a typical target system, the survey achieves median sensitivities 10 mag fainter than the parent star. In terms of companion mass, the survey achieves typical sensitivities of 25M(J) (1 Gyr), 50M(J) ( solar age), and 60M(J) ( 10 Gyr), using the evolutionary models of Baraffe and coworkers. Using common proper motion to distinguish companions from field stars, we find that no systems show positive evidence of a substellar companion (searchable separation similar to 1'' - 15''; projected separation similar to 10 - 155 AU at the median target distance). In the second paper of the series we will present our Monte Carlo population simulations.