A theoretical framework is presented for the interpretation of spin relaxation data from bicontinuous cubic lyotropic phases described by periodic minimal surfaces. Specifically, the two irreducible time correlation functions (TCFs) that determine the contribution from surface diffusion to the observable spin relaxation rates are considered. Simple analytical results are obtained that relate the initial TCFs to the fourth-rank orientational order parameter of the dividing interface and the initial decay of the TCFs to the average Gaussian curvature over the cubic unit cell. These exact results are used to construct single-exponential approximations for the TCFs. Explicit calculations are reported for the three cubic triply periodic minimal surfaces of simplest topology, i.e., Schwarz's D and P surfaces and Schoen's gyroid surface, as well as for the corresponding parallel surfaces that have been used to model the dividing interface (the locus of surfactant headgroups) in bicontinuous cubic phases. The theoretical results presented here demonstrate that spin relaxation data can provide quantitative information about microstructure in bicontinuous cubic phases in surfactant and lipid systems. In particular, the spin relaxation method can discriminate among different microstructures belonging to the same space group, such as the P and C(P) surfaces.