We describe narrowband and spectroscopic searches for emission-line star-forming galaxies in the redshift range 3-6 with the 10 m Keck II Telescope. These searches yield a substantial population of objects with only a single strong (EW much greater than 100 Angstrom) emission line, lying in the 4000-8500 Angstrom range. Spectra of the objects found in narrowband-selected samples at lambda similar to 5390 and similar to 6741 Angstrom show that these Very high equivalent width emission lines are generally redshifted Ly alpha 1216 Angstrom at z similar to 3.4 and 4.5. The density of these emitters above the 5 sigma detection Limit of 1.5 x 10(-17) ergs cm(-2) s(-1) is roughly 15,000 deg(-2) per unit z at both z similar to 3.4 and 4.5. A complementary deeper (1 sigma similar to 10(-18) ergs cm(-2) s(-1)) slit spectroscopic search covering a wide redshift range but a more limited spatial area (200 arcsec(2)) shows that such objects can be found over the redshift range z = 3-6, with the currently highest redshift detected being at z = 5.64. The Ly alpha flux distribution can be used to estimate a minimum star formation rate in the absence of reddening of roughly 0.01 M-. Mpc(-3) yr(-1) (H-o = 65 km s(-1) Mpc(-1), q(o) = 0.5). Corrections for reddening are likely to be no larger than a factor of 2, since observed equivalent widths are close to the maximum values obtainable from ionization by a massive star population. Within the still significant uncertainties, the star formation rate from the Ly alpha-selected sample is comparable to that of the color-break-selected samples at z similar to 3 but may represent an increasing fraction of the total rates at higher redshifts. This higher z population can be readily studied with large ground-based telescopes.