We report the observation of the homogenous nucleation of crystals in a dense layer of steel spheres confined between two horizontal plates vibrated vertically. Above a critical vibration amplitude, two-layer crystals with square symmetry were found to coexist in steady state with a surrounding granular liquid. By analogy to equilibrium hard-sphere systems, the phase behavior may be explained through entropy maximization. However, dramatic nonequilibrium effects are present, including a significant difference in the granular temperatures of the two phases.