The effect of magnetic interactions on the Brownian motion of two magnetic microparticles is investigated. The cross-correlations of the thermal fluctuations of the two magnetic microbeads are directly measured using double-trap optical tweezers. It is experimentally demonstrated that the cross-correlation function is governed by the gradient of the magnetic force between the microparticles. The magnetic forces are measured with femtonewton precision, and the magnetic dipole moments of individual microparticles are determined within an accuracy on the order of fA-m2.