Gaussian graphical models are widely used to infer the partial dependency structure among variables, for example, in gene studies and neuroimaging data. Under this model, conditional independence statements are encoded by zero entries in the model's precision matrix. However, the computational demands of estimating a high-dimensional precision matrix with Bayesian methods have limited the scope of applications when the number of observed variables is large. In this work we consider a parametrisation of the prior distribution based on the discrete spike-and-slab and design scalable Monte-Carlo Markov Chains algorithms for computing the posterior distribution in high-dimensional settings. Our algorithms capitalise on the concentration of the posterior on sparse precision matrices when the ``true'' graphical model is sparse. We also exploit the relationship between the conditional dependence structure and linear regression models to decompose the high-dimensional estimation problem via row-wise computations.  This approach enables us to parallelise some computations of posterior conditional distributions and fosters an efficient exploration of the network structure. Furthermore, we characterise the efficiency of our  Monte-Carlo Markov Chains algorithms in terms of mixing time, using newly developed concepts of conductance for the analysis of Metropolis-within-Gibbs chains (Ascolani et al., 2024).