Interacting quantum many-body systems are usually expected to thermalise, in the sense that the evolution of local expectation values approach a stationary value resembling a thermal ensemble. This intuition is notably contradicted in systems exhibiting many-body localisation, a phenomenon receiving significant recent attention. One of its most intriguing features is that, in stark contrast to the non-interacting case, entanglement of states grows without limit over time, albeit slowly. In this work, we establish a novel link between quantum information theory and notions of condensed matter, capturing the phenomenon in the Heisenberg picture. We show that the existence of local constants of motion, often taken as the defining property of many-body localisation, together with a generic spectrum, is sufficient to rigorously prove information propagation: These systems can be used to send a signal over arbitrary distances, in that the impact of a local perturbation can be detected arbitrarily far away. We perform a detailed perturbation analysis of quasi-local constants of motion and also show that they indeed can be used to construct efficient spectral tensor networks, as recently suggested. Our results provide a detailed and model-independent picture of information propagation in many-body localised systems.