When a ferrofluid is magnetized in a strong magnetic field, and then the field is switched off, the magnetization decays from its saturation value to zero. The dynamics of this process are controlled by the rotations of the constituent magnetic nanoparticles, and for the Brownian mechanism, the respective rotation times are strongly influenced by the particle size and the magnetic dipole-dipole interactions between the particles. In this work, the effects of polydispersity and interactions on the magnetic relaxation are studied using a combination of analytical theory and Brownian dynamics simulations. The theory is based on the Fokker-Planck-Brown equation for Brownian rotation and includes a self-consistent, mean-field treatment of the dipole-dipole interactions. The most interesting predictions from the theory are that, at short times, the relaxation of each particle type is equal to its intrinsic Brownian rotation time, while at long times, each particle type has the same effective relaxation time, which is longer than any of the individual Brownian rotation times. Noninteracting particles, though, always relax at a rate controlled only by the Brownian rotation times. This illustrates the importance of including the effects of polydispersity and interactions when analyzing the results from magnetic relaxometry experiments on real ferrofluids, which are rarely monodisperse.