What is "restricted maximum likelihood" and when should it be used? I have read in the abstract of this paper that:

"The maximum likelihood (ML) procedure of Hartley aud Rao is modified by adapting a transformation from Patterson and Thompson which partitions the likelihood render normality into two parts, one being free of the fixed effects. Maximizing this part yields what are called restricted maximum likelihood (REML) estimators."

I also read in the abstract of this paper that REML:

"takes into account the loss in degrees of freedom resulting from estimating fixed effects."

Sadly I don't have access to the full text of those papers (and probably would not understand if I did).
Also, what are the advantages of REML vs. ML? Under what circumstances may REML be preferred over ML (or vice versa) when fitting a mixed effects model?
Please give an explanation suitable for someone with a high-school (or just beyond) mathematics background!
 A: As per ocram's answer, ML is biased for the estimation of variance components. But observe that the bias gets smaller for larger sample sizes. Hence in answer to your questions "...what are the advantages of REML vs ML ? Under what circumstances may REML be preferred over ML (or vice versa) when fitting a mixed effects model ?", for small sample sizes REML is preferred. However, likelihood ratio tests for REML require exactly the same fixed effects specification in both models. So, to compare models with different fixed effects (a common scenario) with an LR test, ML must be used.
REML takes account of the number of (fixed effects) parameters estimated, losing 1 degree of freedom for each. This is achieved by applying ML to the least squares residuals, which are independent of the fixed effects. 
A: Here is a quick answer...

Standard illustrative example
Let $y = (y_1, \dotsc, y_n)$ be a sample from a normal distribution $\mathrm{N}(\mu, \sigma^2$). Both $\mu$ and $\sigma^2$ are unknown. The maximum likelihood estimator of $\sigma^2$, obtained by taking the derivative of the log-likelihood with respect to $\sigma^2$ and equating to zero, is
$$
\hat{\sigma}^2_{\textrm{ML}} = \frac{1}{n} \sum_{i=1}^n (y_i -\bar{y})^2
$$
where $\bar{y} = \frac{1}{n} \sum_{i=1}^n y_i$ is the maximum likelihood estimator of $\mu$. We can show that
$$
\mathrm{E}(\hat{\sigma}^2_{\textrm{ML}}) = \frac{n-1}{n} \sigma^2.
$$
[Start by rewriting $\hat{\sigma}^2_{\textrm{ML}}$ as $\frac{1}{n} \sum_{i=1}^n \left((y_i - \mu) + (\mu - \bar{y})\right)^2$]. Thus, $\hat{\sigma}^2_{\textrm{ML}}$ is biased. Note that if we had known $\mu$, then the MLE for $\sigma^2$ would have been unbiased. Hence, the problem with $\hat{\sigma}^2_{\textrm{ML}}$ appears to be linked with the fact that we have substituted $\bar{x}$ for the unknown mean in the estimation. The intuitive idea of REML estimation is to end up with a likelihood that contains all the information on $\sigma^2$ but no longer contains the information on $\mu$.
More technically, the REML likelihood is a likelihood of linear combinations of the original data: instead of the likelihood of $y$, we consider the likelihood of $Ky$, where the matrix $K$ is such that
$\mathrm{E}[Ky] = 0$.

REML estimation is often used in the more complicated context of mixed models. Every book on mixed models have a section explaining REML estimation in more details.

Edit
@Joe King: Here (and here, for English web page context) is one of my favorite books on mixed models that is fully available online. Section 2.4.2 deals with estimating variance components. Enjoy your reading :-)
A: ML method underestimates the variance parameters because it assumes that the fixed parameters are known without uncertainty when estimating the variance parameters. 
The REML method uses a mathematical trick to make the estimates for the variance parameters independent of the estimates for the fixed effects.
REML works by first getting regression residuals for the observations modeled by the fixed effects portion of the model, ignoring at this point any variance components.
ML estimates are unbiased for the fixed effects but biased for the random effects, whereas the REML estimates are biased for the fixed effects and unbiased for the random effects. 
