What does it mean that a problem is "NP-complete"?

You can find out all you want and more in a class (or text) on
computational complexity theory.  What "NP-complete" actually is occurs
in paragraph 5 of the following background-heavy short summary:

Problems in computation are classified according to the theoretical
complexity of the best possible (or best known) algorithms for solving
them.  The complexity of a particular problem is "polynomial" if there
exists an algorithm that solves that problem for an input of size "N",
such that the running time of that algorithm is a polynomial function
of N.  For example, the problem of finding a given number in a list of
size N can be solved in (at worst) order(N) time, and "N" is a (very
simple) polynomial function of N.  Thus this problem "is polynomial",
or "can be solved in polynomial time".  This means that this problem is
in the class of problems called "P" (for polynomial).

Sometimes it is possible to show "reductions" from one problem to
another.  That is, given an instance of one problem (A), you show a way
to transform the inputs into those of another problem (B), and also a
way to transform the outputs of problem B into those of problem A.  If
the complexity of doing the transformation does not exceed the
complexity of doing problem B, then you have "reduced" problem A to
problem B, thereby proving that problem A is no more complex than
problem B.

There are problems for which no known polynomial-time algorithm
exists.  For some of them, it can be proven that no polynomial-time
algorithm exists; but for others, this has not been proven.  The
problems for which it is proven that no polynomial-time algorithm exist
are clearly in a class "more complex" than "P".

The others are the interesting ones.  It is not known whether these
problems belong to "P" or not.  Many of these problems -- including the
knapsack problem which started all this -- have been shown by
reductions to be "equivalent".  That is, polynomial-time algorithms for
transforming any one of them to any other of them are known.  (In
practice, many of the transformations are almost trivial.)

So there's this big collection of problems, all of which are
"equivalent" in a computational complexity sense, but it is unknown
just what that complexity is, except that it's "at least" polynomial.
These are the "NP-complete" problems.  If anyone ever finds a
polynomial-time algorithm for any one of these problems, they will have
proven that *all* of the problems belong to "P".  Most computer
scientists believe that this will not happen, though; most think that
they are in a class somewhere "above" "P".

One last thing: colloquially speaking, when someone says "this problem
is NP-complete", they're usually implying something along the lines of
"this is a computationally difficult problem.  If you try to write a
general algorithm that can handle problems of arbitrary size, the
running time of your algorithm will eventually exceed the bounds of
feasible computation, yadda yadda yadda."

-- Tom Magliery <mag@ncsa.uiuc.edu>