This thesis consists of four papers studying structure learning and Bayesian inference in probabilistic graphical models for both undirected and directed acyclic graphs (DAGs). Paper A presents a novel algorithm, called the Christmas tree algorithm (CTA), that incrementally construct junction trees for decomposable graphs by adding one node at a time to the underlying graph. We prove that CTA with positive probability is able to generate all junction trees of any given number of underlying nodes. Importantly for practical applications, we show that the transition probability of the CTA kernel has a computationally tractable expression. Applications of the CTA transition kernel are demonstrated in a sequential Monte Carlo (SMC) setting for counting the number of decomposable graphs. Paper B presents the SMC scheme in a more general setting specifically designed for approximating distributions over decomposable graphs. The transition kernel from CTA from Paper A is incorporated as proposal kernel. To improve the traditional SMC algorithm, a particle Gibbs sampler with a systematic refreshment step is further proposed. A simulation study is performed for approximate graph posterior inference within both log-linear and decomposable Gaussian graphical models showing efficiency of the suggested methodology in both cases. Paper C explores the particle Gibbs sampling scheme of Paper B for approximate posterior computations in the Bayesian predictive classification framework. Specifically, Bayesian model averaging (BMA) based on the posterior exploration of the class-specific model is incorporated into the predictive classifier to take full account of the model uncertainty. For each class, the dependence structure underlying the observed features is represented by a distribution over the space of decomposable graphs. Due to the intractability of explicit expression, averaging over the approximated graph posterior is performed. The proposed BMA classifier reveals superior performance compared to the ordinary Bayesian predictive classifier that does not account for the model uncertainty, as well as to a number of out-of-the-box classifiers. Paper D develops a novel prior distribution over DAGs with the ability to express prior knowledge in terms of graph layerings. In conjunction with the prior, a stochastic optimization algorithm based on the layering property of DAGs is developed for performing structure learning in Bayesian networks. A simulation study shows that the algorithm along with the prior has superior performance compared with existing priors when used for learning graph with a clearly layered structure. / <p>QC 20170915</p>