This paper addresses the question of making inferences regarding features of conditional independence graphs in settings characterized by the availability of rich prior information regarding such features. We focus on Bayesian networks, and use Markov chain Monte Carlo to draw samples from the relevant posterior over graphs. We introduce a class of "locally-informative priors" which are highly flexible and capable of taking account of specific information regarding graph features, and are, in addition, informative at a scale appropriate to local sampling moves. We present examples of such priors for beliefs regarding edges, groups and classes of edges, degree distributions and sparsity, applying our methods to challenging synthetic data as well as data obtained from a biological network in cancer.