Kernel methods have revolutionized the fields of pattern recognition and machine learning. The importance of achieving a sound quantification of uncertainty in predictions by characterizing the posterior distribution over kernel parameters exactly has been demonstrated in several applications. In this talk, I will focus on Markov chain Monte Carlo (MCMC) based inference of covariance (kernel) parameters for Gaussian Process Classifiers (GPCs). After motivating this choice, I will discuss the challenges in employing MCMC methods to obtain samples from the posterior distribution over covariance parameters in GPCs. I will then present the so called Exact-Approximate MCMC approach that offers a practical solution to this problem. In particular, such an approach yields samples from the correct posterior distribution over covariance parameters, but the intractable marginal likelihood in the Hastings ratio is replaced by an easy-to-compute unbiased estimate. I will present practical ways to construct unbiased estimates of the marginal likelihood, and conclude the talk by presenting results on several benchmark data sets and on a multi-class multiple-kernel classification problem on neuroimaging data.