Matérn Gaussian fields are popular modeling choices in many aspects of Bayesian inverse problems, spatial statistics, machine learning, and numerous other scientific applications. In this thesis we investigate their generalizations to graphical domains, referred to as graph Matérn fields, by addressing their construction, application and theoretical properties. Graph Matérn fields share qualitatively similar features with the usual Matérn Gaussian fields on Euclidean spaces that are desirable for modeling purposes and enjoy a sparsity property that facilitates computation. Their wide applicability is demonstrated through several applications including precipitation modeling, an elliptic inverse problem, and semi-supervised classification, bridging together, and promoting exchange of ideas between spatial statistics, Bayesian inverse problems, and graph-based machine learning. Under an assumption that the graph nodes are sampled from a low-dimensional manifold, we show that our graph Matérn fields are consistent approximations of certain Matérn-type Gaussian fields defined over the underlying manifold. Study of the approximation error leads to new insights for the role of the unlabeled data in graph-based semi-supervised learning. Finally we complement the graph-based methods with a denoising algorithm that provably improves the performance when the graph nodes are noisy perturbations of manifold samples, which represents a more realistic scenario in many applications.