The answers provided before are very helpful and detailed. Here is my $0.25.
Confidence interval (CI) is a concept based on the classical definition of probability (also called the "Frequentist definition") that probability is like proportion and is based on the axiomatic system of Kolmogrov (and others).
Credibile intervals (HPD) can be considered to have its roots in decision theory, based on the works of Wald and de Finetti (and extended a lot by others).
As people in this thread have done a great job in giving examples and the difference of hypotheses in the Bayesian and frequentist case, I will just stress on a few important points.
CIs are based on the fact that inference MUST be made on all possible repetitions of an experiment that can be seen and NOT only on the observed data where as HPDs are based ENTIRELY on the observed data (and obv. our prior assumptions).
In general CIs are NOT coherent (will be explained later) where as HPDs are coherent(due to their roots in decision theory). Coherence (as I would explain to my grand mom) means: given a betting problem on a parameter value, if a classical statistician (frequentist) bets on CI and a bayesian bets on HPDs, the frequentist IS BOUND to lose (excluding the trivial case when HPD = CI). In short, if you want to summarize the findings of your experiement as a probability based on the data, the probability HAS to be a posterior probability (based on a prior). There is a theorem (cf Heath and Sudderth, Annals of Statistics, 1978) which (roughly) states: Assignment of probability to $\theta$ based on data will not make a sure loser if and only if it is obtained in a bayesian way.
As CIs don't condition on the observed data (also called "Conditionality Principle" CP), there can be paradoxical examples. Fisher was a big supporter of CP and also found a lot of paradoxical examples when this was NOT followed (as in the case of CI). This is the reason why he used p-values for inference, as opposed to CI. In his view p-values were based on the observed data (much can be said about p-values, but that is not the focus here). Two of the very famous paradoxical examples are: (4 and 5)
Cox's example (Annals of Math. Stat., 1958): $X_i \sim \mathcal{N}(\mu, \sigma^2)$ (iid) for $i\in\{1,\dots,n\}$ and we want to estimate $\mu$. $n$ is NOT fixed and is chosen by tossing a coin. If coin toss results in H, 2 is chosen, otherwise 1000 is chosen. The "common sense" estimate - sample mean is an unbiased estimate with a variance of $0.5\sigma^2+0.0005\sigma^2$. What do we use as the variance of sample mean when $n = 1000$? Isn't it better (or sensible) to use the variance of sample mean estimator as $0.001\sigma^2$ (conditional variance) instead of the actual variance of the estimator, which is HUGE!! ($0.5\sigma^2+0.0005\sigma^2$). This is a simple illustration of CP when we use the variance as $0.001\sigma^2$ when $n=1000$. $n$ stand alone has no importance or no information for $\mu$ and $\sigma$ (ie $n$ is ancillary for them) but GIVEN its value, you know a lot about the "quality of data". This directly relates to CI as they involve the variance which should not be conditioned on $n$, ie we will end up using the larger variance, hence over conservative.
Welch's example: This example works for any $n$, but we will take $n=2$ for simplicity. $X_1, X_2 \sim \mathcal{U}(\theta - 1/2, \theta +1/2)$ (iid), $\theta$ belongs to the Real line. This implies $X_1 - \theta \sim \mathcal{U}(-1/2, 1/2)$ (iid). $\frac{1}{2}(X_1 + X_2) {\bar x} - \theta$ (note that this is NOT a statistic) has a distribution independent of $\theta$. We can choose $c > 0$ s.t. $\text{Prob}_\theta(-c <= {\bar x} - \theta <= c) = 1-\alpha (\approx 99\%)$, implying $({\bar x} - c, {\bar x} + c)$ is the 99% CI of $\theta$. The interpretation of this CI is: if we sample repeatedly, we will get different ${\bar x}$ and 99% (at least) times it will contain true $\theta$, BUT (the elephant in the room) for a GIVEN data, we DON'T know the probability that CI will contain true $\theta$. Now, consider the following data: $X_1 = 0$ and $X_2=1$, as $|X_1 - X_2|=1$, we know FOR SURE that the interval $(X_1, X_2)$ contains $\theta$ (one possible criticism, $\text{Prob}(|X_1 - X_2|=1) = 0$, but we can handle it mathematically and I won't discuss it). This example also illustrates the concept of coherence beautifully. If you are a classical statistician, you will definitely bet on the 99% CI without looking at the value of $|X_1 - X_2|$ (assuming you are true to your profession). However, a bayesian will bet on the CI only if the value of $|X_1 - X_2|$ is close to 1. If we condition on $|X_1 - X_2|$, the interval is coherent and the player won't be a sure loser any longer (similar to the theorem by Heath and Sudderth).
Fisher had a recommendation for such problems - use CP. For the Welch's example, Fisher suggested to condition of $X_2-X_1$. As we see, $X_2-X_1$ is ancillary for $\theta$, but it provides information about theta. If $X_2-X_1$ is SMALL, there is not a lot of information about $\theta$ in the data. If $X_2-X_1$ is LARGE, there is a lot of information about $\theta$ in the data. Fisher extended the strategy of conditioning on the ancillary statistic to a general theory called Fiducial Inference (also called his greatest failure, cf Zabell, Stat. Sci. 1992), but it didn't become popular due to lack of generality and flexibility. Fisher was trying to find a way different from both the classical statistics (of Neyman School) and the bayesian school (hence the famous adage from Savage: "Fisher wanted to make a Bayesian omelette (ie using CP) without breaking the Bayesian eggs"). Folklore (no proof) says: Fisher in his debates attacked Neyman (for Type I and Type II error and CI) by calling him a Quality Control guy rather than a Scientist, as Neyman's methods didn't condition on the observed data, instead looked at all possible repetitions.
Statisticians also want to use Sufficiency Principle (SP) in addition to the CP. But SP and CP together imply the Likelihood Principle (LP) (cf Birnbaum, JASA, 1962) ie given CP and SP, one must ignore the sample space and look at the likelihood function only. Thus, we only need to look at the given data and NOT at the whole sample space (looking at whole sample space is in a way similar to repeated sampling). This has led to concept like Observed Fisher Information (cf. Efron and Hinkley, AS, 1978) which measure the information about the data from a frequentist perspective. The amount of information in the data is a bayesian concept (and hence related to HPD), instead of CI.
Kiefer did some foundational work on CI in the late 1970s, but his extensions haven't become popular. A good source of reference is Berger ("Could Fisher, Neyman and Jeffreys agree about testing of hypotheses", Stat Sci, 2003).
Summary:
(As pointed out by Srikant and others)
CIs can't be interpreted as probability and they don't tell anything about the unkown parameter GIVEN the observed data. CIs are statements about repeated experiments.
HPDs are probabilistic intervals based on the posterior distribution of the unknown parameter and have a probability based interpretation based on the given data.
Frequentist property (repeated sampling) property is a desirable property and HPDs (with appropriate priors) and CI both have them. HPDs condition on the given data also in answering the questions about the unknown parameter
(Objective NOT Subjective) Bayesians agree with the classical statisticians that there is a single TRUE value of the parameter. However, they both differ in the way they make inference about this true parameter.
Bayesian HPDs give us a good way of conditioning on data, but if they fail to agree with the frequentist properties of CI they are not very useful (analalogy: a person who uses HPDs (with some prior) without a good frequentist property, is bound to be doomed like a carpenter who only cares about the hammer and forgets the screw driver)
At last, I have seen people in this thread (comments by Dr. Joris: "...assumptions involved imply a diffuse prior, i.e. a complete lack of knowledge about the true parameter.") talking about lack of knowledge about the true parameter being equivalent to using a diffuse prior. I DONT know if I can agree with the statement (Dr. Keith agrees with me). For example, in the basic linear models case, some distributions can be obtained by using a uniform prior (which some people called diffuse), BUT it DOESN'T mean that uniform distribution can be regarded as a LOW INFORMATION PRIOR. In general, NON-INFORMATIVE(Objective) prior doesn't mean it has low information about the parameter.
Note: A lot of these points are based on the lectures by one of the prominent bayesians. I am still a student and could have misunderstood him in some way. Also, I could not figure how to insert mathematical equations in my comments. Please accept my apologies in advance.
