In Gaussian graphical models, the zero entries in the precision matrix determine the dependence structure, so estimating that sparse precision matrix and, thereby, learning this underlying structure, is an important and challenging problem. We propose an empirical version of the G-Wishart prior for sparse precision matrices, where the prior mode is informed by the data in a suitable way. Paired with a prior on the structure, a marginal posterior distribution for the structure is obtained that takes the form of a ratio of two G-Wishart normalizing constants. We show that this ratio can be readily evaluated using an accurate Laplace approximation, which leads to fast and efficient posterior sampling even in high-dimensions. Numerical results demonstrate the proposed method's superior performance, in terms of speed and accuracy, across a variety of settings, and theoretical support is provided in the form of a posterior concentration rate theorem.