Debris management is one of the most time consuming and complicated activities among post-disaster operations. Debris clearance is aimed at pushing the debris to the sides of the roads so that relief distribution and search-and-rescue operations can be maintained in a timely manner. Given the limited resources, uncertainty, and urgency during disaster response, efficient and effective planning of debris clearance to achieve connectivity between relief demand and supply is important. In this paper, we define the stochastic debris clearance problem (SDCP), which captures post-disaster situations where the limited information on the debris amounts along the roads is updated as clearance activities proceed. The main decision in SDCP is to determine a sequence of roads to clear in each period such that benefit accrued by satisfying relief demand is maximized. To solve SDCP to optimality, we develop a partially observable Markov decision process model. We then propose a heuristic based on a continuous-time approximation, and we further reduce the computational burden by applying a limited look ahead on the search tree and heuristic pruning. The performance of these approaches is tested on randomly generated instances that reflect various geographical and information settings, and instances based on a real-world earthquake scenario. The results of these experiments underline the importance of applying a stochastic approach and indicate significant improvements over heuristics that mimic the current practice for debris clearance.