Our team is carrying out a multi-year observing program to directly image and characterize young extrasolar planets using the Near-Infrared Coronagraphic Imager (NICI) on the Gemini-South 8.1-meter telescope. NICI is the first instrument on a large telescope designed from the outset for high-contrast imaging, comprising a high-performance curvature adaptive optics system with a simultaneous dual-channel coronagraphic imager. Combined with state-of-the-art observing methods and data processing, NICI typically achieves ~2 magnitudes better contrast compared to previous ground-based or space-based programs, at separations inside of ~2 arcsec. In preparation for the Campaign, we carried out efforts to identify previously unrecognized young stars, to rigorously construct our observing strategy, and to optimize the combination of angular and spectral differential imaging. The Planet-Finding Campaign is in its second year, with first-epoch imaging of 174 stars already obtained out of a total sample of 300 stars. We describe the Campaigns goals, design, implementation, performance, and preliminary results. The NICI Campaign represents the largest and most sensitive imaging survey to date for massive (~1 Mjup) planets around other stars. Upon completion, the Campaign will establish the best measurements to date on the properties of young gas-giant planets at ~5-10 AU separations. Finally, Campaign discoveries will be well-suited to long-term orbital monitoring and detailed spectrophotometric followup with next-generation planet-finding instruments.