Why are p-values uniformly distributed under the null hypothesis? Recently, I have found in a paper by Klammer, et al. a statement that p-values should be uniformly distributed. I believe the authors, but cannot understand why it is so. 
Klammer, A. A., Park, C. Y., and Stafford Noble, W. (2009) Statistical Calibration of the SEQUEST XCorr Function. Journal of Proteome Research. 8(4): 2106–2113.
 A: Simple simulation of distribution of p-values in case of linear regression between two independent variables :
# estimated model is: y = a0 + a1*x + e

obs<-100                # obs in each single regression
Nloops<-1000            # number of experiments
output<-numeric(Nloops) # vector holding p-values of estimated a1 parameter from Nloops experiments

for(i in seq_along(output)){

x<-rnorm(obs) 
y<-rnorm(obs)

# x and y are independent, so null hypothesis is true
output[i] <-(summary(lm(y~x)) $ coefficients)[2,4] # we grab p-value of a1

if(i%%100==0){cat(i,"from",Nloops,date(),"\n")} # after each 100 iteration info is printed

}

plot(hist(output), main="Histogram of a1 p-values")
ks.test(output,"punif") # Null hypothesis is that output distr. is uniform

A: Under the null hypothesis, your test statistic $T$ has the distribution $F(t)$ (e.g., standard normal). We show that the p-value $P=F(T)$ has a probability distribution
$$\begin{equation*} \Pr(P < p) = \Pr(F^{-1}(P) < F^{-1}(p)) = \Pr(T < t) \equiv p; \end{equation*}$$
in other words, $P$ is distributed uniformly. This holds so long as $F(\cdot)$ is invertible, a necessary condition of which is that $T$ is not a discrete random variable.
This result is general: the distribution of an invertible CDF of a random variable is uniform on $[0,1]$.
A: Let $T$ denote the random variable with cumulative distribution function $F(t) \equiv \Pr(T<t)$ for all $t$. Assuming that $F$ is invertible we can derive distribution of the random p-value $P = F(T)$ as follows:
$$
\Pr(P<p) = \Pr(F(T) < p) = \Pr(T < F^{-1}(p)) = F(F^{-1}(p)) = p,
$$
from which we can conclude that the distribution of $P$ is uniform on $[0,1]$.
This answer is similar to Charlie's, but avoids having to define $t = F^{-1}(p)$.
A: I think the answer as to "Why are p-values uniformly distributed under the null hypothesis?" has been sufficiently discussed from a mathematical perspective. What I thought is missing is a visual explanation of this and the idea of thinking of p-values as areas to the left of a set of quantiles under a given continuous distribution (probability density function). By quantiles I mean cut-off points along a distribution (in this example the standard normal distribution), which split the distribution into equal parts containing exactly the same area under the curve.
For this example, I generated 100 random data points from the standard normal distribution with a mean of 0 and a standard deviation of 1, $\mathcal{N}(\mu = 0, \sigma = 1)$. Then I plotted those points in a histogram and we can see a bell-shaped distribution forming (Fig. 1A). Then I calculated the p-values of those points, i.e. the areas to the left of those points given the standard normal distribution, plotted those p-values in a histogram (Fig. 1B) and a uniform(ish) distribution is emerging binning those p-values in 0.1 intervals.
This step, i.e. the step from Fig 1A to Fig 1B is puzzling for many people and has been for me as well for some time - until I started thinking of p-values as areas under the curve. My thought was that if I split the standard normal distribution into equal chunks containing the same area (in this case 0.1 to match the histogram in Fig 1B), I will have larger intervals in the tails (Fig 1C). Now if I go back to Fig 1A, I will be able to fit all points ranging from -4 to -1.28 (the interval in Fig 1C) into the first bin of Fig 1B since they all result into areas (or p-values) of less than or equal to 0.1. As the density of points is increasing towards the mean, the intervals that cover an area of 0.1 are becoming increasingly smaller (Fig 1C) but the number of points in those intervals remains roughly equal and in this case matches the count in Fig 1B.

Once I understood this it was also easy for me to explain why a random sample of 100 points from a normal distribution with mean of 0 and a standard deviation of 3, $\mathcal{N}(\mu = 0, \sigma = 3)$ results into a higher frequency of p-values around 0 and 1 or in the tails (Fig 2B). The reason is that the p-values are calculated based on the standard normal distribution yet the sample comes from a normal distribution with mean of 0 and a standard deviation of 3. This will result into many more points in the tails than it would be for a sample coming from the standard normal distribution.

I hope this was not overly confusing and added some value to this thread.
A: To clarify a bit.  The p-value is uniformly distributed when the null hypothesis is true and all other assumptions are met.  The reason for this is really the definition of alpha as the probability of a type I error.  We want the probability of rejecting a true null hypothesis to be alpha, we reject when the observed $\text{p-value} < \alpha$, the only way this happens for any value of alpha is when the p-value comes from a uniform distribution.  The whole point of using the correct distribution (normal, t, f, chisq, etc.) is to transform from the test statistic to a uniform p-value.  If the null hypothesis is false then the distribution of the p-value will (hopefully) be more weighted towards 0.
The Pvalue.norm.sim and Pvalue.binom.sim functions in the TeachingDemos package for R will simulate several data sets, compute the p-values and plot them to demonstrate this idea. 
Also see: 

Murdoch, D, Tsai, Y, and Adcock, J (2008). P-Values are Random
  Variables. The American Statistician, 62, 242-245.

for some more details.
Edit:
Since people are still reading this answer and commenting, I thought that I would address @whuber's comment.
It is true that when using a composite null hypothesis like $\mu_1 \leq \mu_2$ that the p-values will only be uniformly distributed when the 2 means are exactly equal and will not be a uniform if $\mu_1$ is any value that is less than $\mu_2$.  This can easily be seen using the Pvalue.norm.sim function and setting it to do a one sided test and simulating with the simulation and hypothesized means different (but in the direction to make the null true).
As far as statistical theory goes, this does not matter.  Consider if I claimed that I am taller than every member of your family, one way to test this claim would be to compare my height to the height of each member of your family one at a time.  Another option would be to find the member of your family that is the tallest and compare their height with mine.  If I am taller than that one person then I am taller than the rest as well and my claim is true, if I am not taller than that one person then my claim is false.  Testing a composite null can be seen as a similar process, rather than testing all the possible combinations where $\mu_1 \leq \mu_2$ we can test just the equality part because if we can reject that $\mu_1 = \mu_2$ in favour of $\mu_1 > \mu_2$ then we know that we can also reject all the possibilities of $\mu_1 < \mu_2$.   If we look at the distribution of p-values for cases where $\mu_1 < \mu_2$ then the distribution will not be perfectly uniform but will have more values closer to 1 than to 0 meaning that the probability of a type I error will be less than the selected $\alpha$ value making it a conservative test.  The uniform becomes the limiting distribution as $\mu_1$ gets closer to $\mu_2$ (the people who are more current on the stat-theory terms could probably state this better in terms of distributional supremum or something like that).  So by constructing our test assuming the equal part of the null even when the null is composite, then we are designing our test to have a probability of a type I error that is at most $\alpha$ for any conditions where the null is true.
