Spatio-temporal data sets such as satellite image series are of utmost importance for understanding global developments like climate change or urbanization. However, incompleteness of data can greatly impact usability and knowledge discovery. We in fact consider cases in which no single data point in the set is fully observed. For filling gaps, we introduce a novel approach which utilizes Markov random fields (MRFs). To handle such highly incomplete data during training, we present new methods to incorporate prior knowledge into the probabilistic framework. Moreover, we devise a way to make discrete MRFs predict continuous values via state superposition. Experiments on real-world remote sensing imagery suffering from cloud cover show that the proposed approach outperforms state-of-the-art gap filling techniques.