Kernel Regression over Graphs (KRG) was recently proposed for predicting graph signals in a supervised learning setting, where the inputs are agnostic to the graph. KRG model predicts targets that are smooth graph signals as over the given graph, given the input when all the signals are deterministic. In this work, we consider the development of a stochastic or Bayesian variant of KRG. Using priors and likelihood functions, our goal is to systematically derive a predictive distribution for the smooth graph signal target given the training data and a new input. We show that this naturally results in a Gaussian process formulation which we call Gaussian Processes over Graphs (GPG). Experiments with real-world datasets show that the performance of GPG is superior to a conventional Gaussian Process (without the graph-structure) for small training data sizes and under noisy training.