The exploration of the universe has recently entered a new era thanks to the multi-messenger paradigm, characterized by a continuous increase in the quantity and quality of experimental data, that is obtained by the detection of the cosmic messengers (photons, neutrinos, cosmic rays, and gravitational waves) from numerous origins. They give us information about their sources in the universe and the properties of the intergalactic medium. Moreover, multi-messenger astronomy opens up the possibility to search for phenomenological signatures of quantum gravity. On the one hand, the most energetic events allow us to test our physical theories at energy regimes that are not directly accessible in accelerators; on the other hand, tiny effects in the propagation of very high energy particles could be amplified by cosmological distances. After decades of merely theoretical investigations, the possibility of obtaining phenomenological indications of Planck-scale effects is a revolutionary step in the quest for a quantum theory of gravity, but it requires cooperation between different communities of physicists (both theoretical and experimental). This review is aimed at promoting this cooperation by giving a state-of-the art account of the interdisciplinary expertise that is needed in the effective search of quantum gravity footprints in the production, propagation and detection of cosmic messengers.