Neutrinos undergoing stochastic perturbations as they propagate experience decoherence, damping neutrino oscillations over distance. Such perturbations may result from fluctuations in space-time itself if gravity is a quantum force, including interactions between neutrinos and virtual black holes. In this work we model the influence of heuristic neutrino-virtual black hole interaction scenarios on neutrino propagation and evaluate the resulting signals in astrophysical and atmospheric neutrinos. We derive decoherence operators representing these effects in the framework of open quantum systems, allowing experimental constraints on such systems to be connected to quantum gravitational effects. Finally, we consider the energy-dependence of such Planck scale physics at energies observed in current neutrino experiments, and show that sensitivity to Planck scale physics well below the "natural" expectation is achievable in certain scenarios.