There is a wealth of cosmological information encoded in the spatial power spectrum of temperature anisotropies of the cosmic microwave background. Originally detected by the COBE satellite, the brightness fluctuations in the microwave sky have now been mapped by ground, balloon, and satellite instruments to a spatial resolution smaller than 1 degree. These brightness fluctuations trace small density perturbations in the early universe (roughly 300,000 years after the Big Bang), which later grow through gravitational instability to the large-scale structure seen in redshift surveys. The details of the physics in the early universe leaves a telltale signature on the statistical structure of hot and cold spots, with more details of the physics encoded at sub-angular degree spatial scales. With the push to map the microwave sky at higher spatial resolution has come a flood of data, with maps containing millions of pixels observed at several different frequencies (from 30 to 900 GHz), all with slightly different resolutions and noise properties. The resulting analysis challenge is to estimate, and quantify our uncertainty in, the spatial power spectrum of the cosmic microwave background given the complexities of "missing data", foreground emission, and complicated instrumental noise. In this talk, I will review a Bayesian formulation of this problem and its numerical implementation with Gibbs sampling from the posterior given the data. In addition I will discuss the limitations of Gibbs sampling, and report on the development of an adaptive Monte Carlo approach, allowing the entire past history of computation to be used in generating the next generation of samples from the posterior.