We investigate the power spectrum of the distortion of the cosmic microwave background (CMB) due to the decay of the primordial magnetic fields. It is known that there are two types of the CMB distortions, so-called mu and y types, and we find that the signal of the y-type distortion becomes larger than that of the mu-type one. We also discuss cross power spectra between the CMB distortions and the CMB temperature anisotropy, which are naturally generated due to the existence of the primordial magnetic fields. We find that such cross power spectra have small amplitudes compared with the autopower spectra of the CMB distortions because of the Silk damping effect of the temperature anisotropy. We also investigate the possibility of detecting such a signal in the future CMB experiments, including not only absolutely calibrated experiments such as PIXIE but also relatively calibrated experiments such as LiteBIRD and CMBpol.