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 (AO) system with a simultaneous dual-channel coronagraphic imager. Combined with state-of-the-art AO observing methods and data processing, NICI typically achieves approximate to 2 magnitudes better contrast compared to previous ground-based or space-based planet-finding efforts, at separations inside of approximate to 2 ''. In preparation for the Campaign, we carried out efforts to identify previously unrecognized young stars as targets, to develop a rigorous quantitative method for constructing our observing strategy, and to optimize the combination of angular differential imaging 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 Campaign's goals, design, target selection, implementation, on-sky performance, and preliminary results. The NICI Planet-Finding Campaign represents the largest and most sensitive imaging survey to date for massive (greater than or similar to 1 M-Jup) planets around other stars. Upon completion, the Campaign will establish the best measurements to date on the properties of young gas-giant planets at greater than or similar to 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.