In 21 cm cosmology, precision calibration is key to the separation of the neutral hydrogen signal from bright astrophysical foregrounds. If not properly calibrated, each antenna element's complex gain can impart spectral structure on otherwise spectrally-smooth foregrounds, complicating that statistical separation. The Hydrogen Epoch of Reionization Array (HERA), an interferometer specialized for 21 cm cosmology and now under construction in South Africa, was designed to be largely calibrated using the self-consistency of repeated measurements of the same interferometric modes. This technique, known as redundant-baseline calibration resolves most of the internal degrees of freedom in the calibration problem. It assumes, however, on antenna elements with identical primary beams placed precisely on a redundant grid. In this work, we review the detailed implementation of the algorithms enabling redundant-baseline calibration and report results with HERA data. We quantify the effects of real-world non-redundancy and how they compare to the idealized scenario in which redundant measurements differ only in their noise realizations. Finally, we study how non-redundancy can produce spurious temporal structure in our calibration solutions---both in data and in simulations---and present strategies for mitigating that structure.