We present deep near-infrared images of high-redshift radio galaxies (HzRGs) obtained with the near-infrared camera (NIRC) on the Keck I telescope. In most cases, the near-IR data sample rest wavelengths that are free of contamination from strong emission lines and at lambda(rest) > 4000 Angstrom, where older stellar populations, if present, might dominate the observed flux. At z > 3, the rest-frame optical morphologies generally have faint, large-scale (similar to 50 kpc) emission surrounding multiple, similar to 10 kpc components. The brightest of these components are often aligned with the radio structures. These morphologies change dramatically at 2 < z < 3, where the K-band images show single, compact structures without bright, radio-aligned features. The linear sizes (similar to 10 kpc) and luminosities [M(B-rest) similar to -20 to -22] of the individual components in the z > 3 HzRGs are similar to the total sizes and luminosities of normal radio-quiet star forming galaxies at z = 3-4. For objects where such data are available, our observations show that the line-free, near-IR colors of the z > 3 galaxies are very blue, consistent with models in which recent star formation dominates the observed light. Direct spectroscopic evidence for massive star formation in one of the z > 3 HzRGs exists (4C 41.17). Our results suggest that the z > 3 HzRGs evolve into much more massive systems than the radio-quiet galaxies and that they are qualitatively consistent with models in which massive galaxies form in hierarchical fashion through the merging of smaller star-forming systems. The presence of relatively luminous subcomponents along the radio axes of the z > 3 galaxies suggests a causal connection with the AGN. We compare the radio and near-IR sizes as a function of redshift and suggest that this parameter may be a measure of the degree to which the radio sources have induced star formation in the parent objects. We also discuss the Hubble diagram of radio galaxies, the possibility of a radio power dependence in the K-z relation, and its implications for radio galaxy formation. Finally, we present for the first time in published format basic radio and optical information on 3C 257 (z = 2.474), the highest redshift galaxy in the 3C sample and among the most powerful radio sources known.