We study the matter effects on oscillations of high-energy neutrinos in the Universe. A substantial effect can be produced by scattering of the neutrinos from cosmological sources (z greater than or similar to1) on the relic neutrino background, provided that the latter has large CP asymmetry: eta=(n(v)-n((v) over bar))/n(gamma)greater than or similar to1, where n(v), n((v) over bar),-, and n(gamma) are the concentrations of neutrinos, antineutrinos, and photons. We consider in detail the dynamics of conversion in the expanding neutrino background, Applications are given to the diffuse fluxes of neutrinos from gamma ray bursters, active galactic nuclei, and the decay of superheavy relics. We find that the vacuum oscillation probability can be modified by similar to 10-20%, and in extreme cases allowed by present bounds on eta the effect can reach 100%. The signatures of matter effects would consist (i) for both active-active and active-sterile conversion, in a deviation of the numbers of events produced in a detector by neutrinos of different flavors, N-alpha (alpha =e,mu,tau), and of their ratios from the values given by vacuum oscillations; such deviations can reach similar to5-15%, and (ii) for active-sterile conversion, in a characteristic energy dependence of the ratios N-e/N-mu,N-e/N-tau,N-mu/N-tau. Searches for these matter effects will probe large CP and lepton asymmetries in the Universe.