A theoretical analysis of possible influence of neutrino magnetic moments on the propagation of ultrahigh-energy cosmic neutrinos in the interstellar space is carried out under the assumption of two-neutrino mixing. The exact solution of the effective equation for neutrino evolution in the presence of a magnetic field and matter is obtained, which accounts for four neutrino species corresponding to two different flavor states with positive and negative helicities. Using most stringent astrophysical bounds on the putative neutrino magnetic moment, probabilities of neutrino flavor and spin oscillations are calculated on the basis of the obtained exact solution. Specific patterns of spin-flavor oscillations are determined for neutrino-energy values characteristic of, respectively, the cosmogenic neutrinos, the Greisen-Zatsepin-Kuz'min (GZK) cutoff, and well above the cutoff.