The Reionization Era Bright Emission Line Survey (REBELS) is a cycle-7 ALMA Large Program (LP) that is identifying and performing a first characterization of many of the most luminous star-forming galaxies known in the z>6.5 universe. REBELS is providing this probe by systematically scanning 40 of the brightest UV-selected galaxies identified over a 7-deg**2 area for bright 158-micron [CII] and 88-micron [OIII] lines and dust-continuum emission. Selection of the 40 REBELS targets was done by combining our own and other photometric selections, each of which is subject to extensive vetting using three completely independent sets of photometry and template-fitting codes. Building on the observational strategy deployed in two pilot programs, we are increasing the number of massive interstellar medium (ISM) reservoirs known at z>6.5 by ~4-5x to >30. In this manuscript, we motivate the observational strategy deployed in the REBELS program and present initial results. Based on the 60.6 hours of ALMA observations taken in the first year of the program (November 2019 to January 2020), 18 highly significant >~7sigma [CII] lines have already been discovered, the bulk of which (13/18) also show >~3.3 sigma dust-continuum emission. These newly discovered lines more than triple the number of bright ISM-cooling lines known in the z>6.5 universe, such that the number of ALMA-derived redshifts at z>6.5 already rival Lya redshift discoveries. An analysis of the completeness of our search results vs. star formation rate (SFR) suggests an ~79% efficiency in scanning for [CII] when the SFR(UV+IR) is in excess of 28 M_sol/yr. These new LP results further demonstrate ALMA's efficiency as a "redshift machine", particularly in the epoch of reionization.