What is the Riemann-Zeta function? In laymen's terms, as much as possible: What is the Riemann-Zeta function, and why does it come up so often with relation to prime numbers?
 A: Giving an explanation in layman's terms is always going to be challenging, given that the Riemann-Zeta function (and related hypothesis) inevitably lies in the domain of abstract mathematics, but I shall do my best.
The Riemann-Zeta function is a complex function that tells us many things about the theory of numbers. Its mystery is increased by the fact it has no closed form - i.e. it can't be expressed a single formula that contains other standard (elementary) functions.
Although there are many different ways of expressing the Riemann-Zeta function (the Wikipedia article gives several), it can ultimately be derived from the following simple series of real numbers:
$\displaystyle\sum_{n=1}^\infty\dfrac1{n^s},\quad\Re(s)\gt1$
by extending it into the complex plane.
The reason this strange and esoteric function is so famous and actively discussed in mathematics is due to the Riemann hypothesis - proposed in 1859 by the great Bernhard Riemann and still unsolved. The Wiki article states the problem in quite simple terms:

The Riemann zeta-function ζ(s) is
  defined for all complex numbers s ≠ 1.
  It has zeros at the negative even
  integers (i.e. at s = −2, −4, −6,
  ...). These are called the trivial
  zeros. The Riemann hypothesis is
  concerned with the non-trivial zeros,
  and states that:
The real part of any non-trivial zero of the Riemann zeta function is 1/2.

Thus the non-trivial zeros should lie
  on the critical line, 1/2 + it, where
  t is a real number and i is the
  imaginary unit.

Although the conjecture (it is only that at the moment) has many consequences for mathematics (number theory in particular), the primary one, at least the one Riemann originally proposed, is about the distribution of prime numbers. In other words, it tells us with great precision what the average gaps between primes are as we move to greater and greater numbers. Many of the other implications are rather more esoteric, though perhaps equally important for pure mathematicians.
A: The above answers give excellent explanations about why the zeta function has close connections to number theory, but I thought I'd mention something about why the Riemann Hypothesis should matter so much.
By taking the logarithm and then differentiating the zeta function, one gets the formula
$$\frac{\zeta'(s)}{\zeta(s)}=\sum_{n=1}^\infty\frac{\Lambda(n)}{n^s}$$
for $\Re(s)>1$, where $\Lambda(n)$ is the von Mangoldt function which takes the value $\log p$ at powers of primes $p$, and is 0 everywhere else. Think of it as a weighted way of counting the primes (the prime number theorem tells us that $\log p$ is the natural weight to choose).
Much of analytic number theory proceeds by choosing a weight of the set we wish to consider (often the primes), and then encoding this weighting in a so-called Dirichlet series (an infinite sum of the form above). We can then use analysis to study this series and get lots of useful information.
In this case, then, the function we need to study to get information about the primes is $\frac{\zeta'(s)}{\zeta(s)}$, which we can study using complex analysis.
In complex analysis, a good slogan is 'the only things that matter are zeros and poles' (effectively points where the function shoots off to infinity). 
Hence to understand the prime numbers, we just need to understand the zeros and poles of $\frac{\zeta'(s)}{\zeta(s)}$ - we know about the simple pole at $s=1$, we know there aren't any other zeros where it counts, and we also know that the only other poles are at zeros of $\zeta(s)$ (roughly because dividing by zero causes infinity). 
In other words, if we knew where these zeros are (i.e. the Riemann hypothesis) we can work with $\frac{\zeta'(s)}{\zeta(s)}$ in all kinds of clever ways to get good results on the prime numbers.

More specifically, in the usual contour proof of the prime number theorem, knowing that there aren't any other zeros in $\Re(s)>1/2$ would allow us to shift the contour further to the left, reducing the error term in the result to (roughly) $O(\sqrt{x})$.
A: Here there is another attempt at an explanation.
We know that the sum of the inverse of the positive numbers, $1 + 1/2 + 1/3 + \cdots$, diverges. Euler shown that the sum of the inverse of the squares,  $1/(1^2) + 1/(2^2) + 1/(3^2) + \cdots$, has a finite sum, namely $\pi^2/6$. Mathematicians love to generalize things, so they thought at the function
$\displaystyle f(x)=\sum_{n=1}^\infty\dfrac1{n^x}$
which is defined for $x \gt 1$. But this was not enough: they decided that the variable could be a complex number and not a real one. There is a standard tecnique (Analytic continuation) which allows us to extend the function to nearly all the complex plane. So we now have a function which formally is 
$\displaystyle \zeta(s)=\sum_{n=1}^\infty\dfrac1{n^s}$
(the variable being $s$ and not $x$ to show that we are dealing with complex numbers) but is not computed in this way. Just to make an example, $\zeta(0)=-1/2$, and sum of an infinity of ones is not $-1/2$. :-) 
It may be shown that for $s = -2n$ ($n$ positive integer) $\zeta(s) = 0$. But there are infinite other point $s'=(x,y)$ where $\zeta(s') = 0$. For all of these points, $0 \lt x \lt 1$; Riemann's hypothesis says that for all such points $x = 1/2$. If it were true, we could have the best asymptotic expression to count $\pi(n)$, that is the number of primes below $n$.
Why does the function pop up when we talk about primes? I don't know, but in the case of integer values Euler proved that 
$\displaystyle\sum_{n=1}^\infty\frac1{n^s}=\prod_{p \text{ prime}}\frac1{1-p^{-s}}$
Maybe this could be a good start.
A: The key point is that the Riemann zeta function is a function whose properties encode properties about the prime numbers.  As mentioned by Noldorin, in order to fully understand the Riemann zeta function you need to "analytically continue it to the complex plane" which is a tricky process which takes serious study.  Fortunately for some easier properties of the primes you can just use the definition of the zeta function for real s.
Claim (due to Euler): The fact that $\zeta(s)$ goes to infinity as $s\to 1$ tells you that there are infinitely many primes.
Sketch of proof: Use the "Euler factorization" mentioned by mau (expand the RHS as a geometric series and then multiply it out using unique factorization into primes):
$\displaystyle\sum_{n=1}^\infty \frac{1} {n^s} = \prod_{p\in\text{prime}} \frac{1} {1-p^-s}$
Now take log of both sides to get:
$\displaystyle\log \zeta(s) = \sum_{p\in\text{prime}} \log \frac{1} {1-p^-s}.$
Now use the taylor series for \log and send s to one.  You'll get that the left hand side goes to infinity (Why does the series $\sum_{n=1}^\infty\frac1n$ not converge?), while the right hand side looks like $\sum 1/p$ + bounded terms.  So there must be infinitely many primes.
A: Suppose you want to put a probability distribution on the natural numbers for the purpose of doing number theory.  What properties might you want such a distribution to have?  Well, if you're doing number theory then you want to think of the prime numbers as acting "independently": knowing that a number is divisible by $p$ should give you no information about whether it's divisible by $q$.
That quickly leads you to the following realization: you should choose the exponent of each prime in the prime factorization independently.  So how should you choose these?  It turns out that the probability distribution on the non-negative integers with maximum entropy and a given mean is a geometric distribution, as explained for example by Keith Conrad here.  So let's take the probability that the exponent of $p$ is $k$ to be equal to $(1 - r_p) r_p^k$ for some constant $r_p$.
This gives the probability that a positive integer $n = p_1^{e_1} ... p_k^{e_k}$ occurs as
$\displaystyle C \prod_{i=1}^{k} r_p^{e_i}$
where $C = \prod_p (1 - r_p)$.  So we need to choose $r_p$ such that this product converges.  Now, we'd like the probability that $n$ occurs to be monotonically decreasing as a function of $n$.  It turns out (and this is a nice exercise) that this is true if and only if $r_p = p^{-s}$ for some $s > 1$ (since $C$ has to converge), which gives the probability that $n$ occurs as
$\frac{ \frac{1}{n^s} }{ \zeta(s)}$
where $\zeta(s)$ is the zeta function.  
One way of thinking about this argument is that $\zeta(s)$ is the partition function of a statistical-mechanical system called the Riemann gas.  As $s$ gets closer to $1$, the temperature of this system increases until it would require infinite energy to make $s$ equal to $1$.  But this limit is extremely important to understand: it is the limit in which the probability distribution above gets closer and closer to uniform.  So it's not surprising that you can deduce statistical information about the primes by studying the behavior as $s \to 1$ of this distribution.

Let me mention two other reasons to care about the limit as $s \to 1$ of the above distribution.  First, the basic reason to think of the primes as acting independently is the Chinese Remainder Theorem.  Second, a natural reason to look at a distribution where the probability that a number has exactly $k$ factors of $p$ is $(1 - p^{-1}) p^{-k}$ is that this is precisely the distribution you get on the residues $\bmod p^n$ for $k < n$.  In fact, I believe this can be upgraded to the corresponding statement about Haar measure on the $p$-adic integers.  
