Given a compact metric graph $Γ$ and the Laplacian $Δ_Γ$ coupled with standard (Kirchhoff) vertex conditions, solutions to fractional elliptic partial differential equations of the form $(κ^2 - Δ_Γ)^{α/2}u=f$ on $Γ$ exhibit a distinctive regularity structure: even-order derivatives are continuous across vertices, while odd-order derivatives may be discontinuous. This non-standard smoothness property precludes the direct application of classical tools from real functional analysis. Because of this, we introduce and systematically study new families of Sobolev spaces tailored to this setting. We define these spaces, denoted $W^{α,p}(Γ)$ and $H^α(Γ)$, to respect the continuity constraints on even-order derivatives at vertices, while permitting discontinuities in odd-order derivatives. We establish their fundamental properties, including characterizations, embedding theorems into Hölder and Lebesgue spaces, and compactness results. A central contribution in this investigation is the derivation of uniform bounds on the supremum norm of eigenfunctions for a class of Laplacians on metric graphs, a result of independent interest. Finally, we demonstrate that these spaces provide a natural framework for analyzing the regularity of solutions to fractional elliptic PDEs and SPDEs driven by Gaussian white noise on metric graphs, in particular, establishing a general characterization of the domain of the fractional powers of $(κ^2-Δ_Γ)$ and $(κ^2-\nabla(a\nabla))$ in terms of the Sobolev spaces we introduce, thereby extending all previously known characterizations in the literature, and improving the regularity results previously obtained to their sharp counterparts (with general fractional powers). We also show that these spaces are fundamental to the characterization of Gaussian free fields on metric graphs.