Magnetic fields appear wherever plasma and currents can be found. As such, they thread through all scales in Nature. It is natural, therefore, to suppose that magnetic fields might have been formed within the high temperature environments of the big bang. Such a primordial magnetic field (PMF) would be expected to arise from and/or influence a variety of cosmological phenomena such as inflation, cosmic phase transitions, big bang nucleosynthesis, the cosmic microwave background (CMB) temperature and polarization anisotropies, the cosmic gravity wave background, and the formation of large-scale structure. In this review, we summarize the development of theoretical models for analyzing the observational consequences of a PMF. We also summarize the current state of the art in the search for observational evidence of a PMF. In particular we review the framework needed to calculate the effects of a PMF power spectrum on the CMB and the development of large scale structure. We summarize the current constraints on the PMF amplitude $B_\lambda$ and the power spectral index $n_B$ and discuss prospects for better determining these quantities in the near future.