I simply must to include MCMC in Practice. It provides an excellent introduction to MCMC, perhaps not as general as other books mentioned, but excellent for gaining insight and intuition. I would recommend reading it after (or in parallel with) Bayesian Computation with R.