We report on deep near-infrared (NIR) observations of submillimeter-selected galaxies (SMGs) with the Near Infrared Camera (NIRC) on the Keck I telescope. We have identified K-band candidate counterparts for 12 out of 15 sources in the SCUBA Cluster Lens Survey. Three SMGs remain non-detections with K-band limits of K>23 mag, corrected for lensing. Compensating for lensing we find a median magnitude of K=22+/-1 mag for the SMG population, but the range of NIR flux densities spans more than a factor of 400. For SMGs with confirmed counterparts based on accurate positions from radio, CO, and/or millimeter continuum interferometric observations, the median NIR color is J-K=2.6+/-0.6 mag. The NIR-bright SMGs (K<19 mag) have colors of J-K =~ 2 mag, while the faint SMGs tend to be extremely red in the NIR (J-K>3 mag). We argue that a color selection criterion of J-K>~3 mag can be used to help identify counterparts of SMGs that are undetected at optical and radio wavelengths. The number density of sources with J-K>3 mag is 5 arcmin^{-2} at K<22.5 mag, greater than that of SMGs with S(850um)>2 mJy. It is not clear if the excess represents less luminous infrared-bright galaxies with S(850um)<~2 mJy, or if the faint extremely red NIR galaxies represent a different population of sources that could be spatially related to the SMGs. Comment: Accepted, Astronomical Journal (scheduled for Feb04), 11 pages including 3 figures (fig1a, fig1b, fig2)