Recent experiments have found that homogeneous nucleation occurs in dense granular materials undergoing cyclic shear from an initially disordered state. In the experiments, the mm-sized grains are under gravitational loading and interact via frictional contact forces. In this work, we carry out discrete element method simulations to determine the contributions of friction and gravity to the crystallization of granular materials during cyclic shear. We show that cyclic shear of frictionless granular materials in the absence of gravity gives rise to a first-order-like phase transition from a disordered state to a polycrystalline state with domains of face-centered cubic and hexagonal close-packed positional order. The polycrystalline ordering develops through homogeneous nucleation, i.e., spontaneous formation of crystalline clusters far from the boundaries of the system. The small crystalline clusters typically shrink before they reach a critical size, above which crystallites with no preferred orientation grow to reach the system size. Thus, gravitational loading and frictional forces are not necessary to induce crystallization in driven granular media.