Traditional approaches to probabilistic inference, such as loopy belief propagation and Gibbs sampling, typically compute marginals for all the unobserved variables in a graphical model. However, in many real-world applications the user's interests are more focused and may be specified by a query over a subset of the model's variables. In this case it would be wasteful to uniformly Gibbs sample one million variables in a model when the query concerns only ten variables. In this paper we propose a query-specific approach to MCMC that accounts for the query variables and their generalized mutual information with neighboring variables in order to achieve higher efficiency\cut{while providing provable guarantees on performance}. Surprisingly there has been almost no previous work on query-aware MCMC. We demonstrate the success our approach with positive experimental results on a wide range of graphical models.