This theoretical paper aims to provide a probabilistic framework for graph signal processing. By modeling signals on graphs as Gaussian Markov Random Fields, we present numerous important aspects of graph signal processing, including graph construction, graph transform, graph downsampling, graph prediction, and graph-based regularization, from a probabilistic point of view. As examples, we discuss a number of methods for constructing graphs based on statistics from input data sets; we show that the graph transform is the optimal linear transform to decorrelate the signal; we describe the optimality of the Kron reduction for graph downsampling in a probabilistic sense; and we derive the optimal predictive transform coding scheme applicable to both motion prediction and intra predictive coding.