Newton's Bucket Newton's Bucket
This thought experiment is originally due to Sir Isaac Newton. We have a sphere of water floating freely in an opaque box in intergalactic space, held together by surface tension and not rotating with respect to the distant galaxies. Now we set the box and water to rotate about some axis and we notice that the sphere flattens into an oblate spheroid. 
How does the water know it’s spinning?
NOTE: Newton thought this proved the concept of absolute rotation with respect to a preferred spatial frame of reference. Perhaps these days we can do better, or different?
 A: A synopsis of what Lubos wrote: It is possible to tell what an inertial reference frame is, locally (in an infinitesimal neighborhood of any point of spacetime), with respect to the local gravitational field (it's the one that is "freely falling"). The bucket "knows" that it is rotating because it rotates with respect to the local inertial frame, that is because it "rotates relative to the local gravitational field".
A: If this is really about General Relativity then this is a description of a rotating body in General Relativity. As this question impinges on some issues in my General relativity Stack questions I shall make a few remarks about it.
General Relativity provides a solution (which we can think of for now as a generalised metric) given some conditions: usually matter conditions. Your basic scenario is of a bounded perfect fluid which is understood in GR. The other aspect of your condition is that it is rotating. A google search shows that for bounded matter a full rotational GR solution may not yet be known. The mechanism by which it is studied is that of a perturbation of a non-rotating solution based around the Schwarzchild solution. This is the model for a rotating star and so on.
The matter in the solution will follow the metric, which has curved spacetime inside and around the fluid. The surface tension and other things like that are meant to be incorporated in the Stress-Energy Tensor: if those features are present the fluid isnt perfect, and so another layer of approximation is used in practice.
I believe that this rotating scenario also generates (weak) gravitational waves!
A: Dear Nigel, Newton had to postulate an absolute space. In fact, he used his physics insights to support the idea of a "spirit" that is filling the space - a paradigm this greatest scientist and a devoted Christian was as passionate about as about physics itself. The absolute space determined geometry everywhere except that it didn't know about any preferred velocity; it only knew about preferred accelerations. 
Inertial systems in classical physics
Newton's laws of physics were valid in inertial frames only. If the laws have the usual forms in one frame, one can show that they also have the same form in all frames that are moving by a constant speed in the same direction. But one can also show that the form of the laws changes if we switch to a different system that is accelerating or spinning because this system is not inertial.
The difference between inertial and non-inertial frames is surely a basic postulate of classical mechanics and it is one that is extremely well established by the experiments, too. Newton's bucket is one of the simple ways to show that rotating frames and non-rotating frames simply differ, so the hypothesis (assumed in between lines of your question) that there is a "complete democracy" between all frames, regardless of their rotation, is instantly falsified.
Special relativity
Similar "absolute structures" filling space and time survived in relativity as well, despite Einstein's original fascination with the so-called Mach's principle that de facto wanted to deny that the rotating bucket behaves differently than the non-rotating one. General relativity ultimately rejected Mach's principle even though one may see some individual effects - memories - predicted by general relativity that are similar to those discussed by Mach.
In special relativity, there exists a "metric tensor" in the whole spacetime that tells all the buckets - and all other objects - whether they're rotating (and accelerating) or not. If they're not rotating, the metric will be given by 
$$\eta(x,y,z,t)=\mbox{diag}(-1,+1,+1,+1)$$
I chose the sign convention randomly. However, if one transforms this metric to a frame that is inertial - it is spinning or accelerating - the metric tensor will be transformed into a different one, namely a set of 10 non-constant functions.
General relativity
The very same thing is true in general relativity where the metric tensor becomes dynamical and may be curved by the presence of heavy objects. It is still true that the metric in non-rotating frames will be given by 
$$ds^2 =-c^2dt^2+dx^2+dy^2+dz^2$$
which is just a different way of writing the metric $\eta$ a few lines above. However, if one transforms this metric tensor to a spinning frame, one gets a different metric tensor. The deviation from the flat space metric may be interpreted as a "gravitational field". The equivalence principle guarantees that the effect of gravitational fields is indistinguishable from the effect of inertial forces resulting from spin or acceleration.
So the extra corrections in the metric tensor will know all about the centrifugal, centripetal, and Coriolis forces that are responsible for the modified shape of the water surface, among many other effects.
To summarize, the bucket - and all other objects - know how to behave and whether they're spinning because they interact with the metric tensor that fills the whole spacetime and that allows one to distinguish straight lines (or world lines) from the curved lines (or world lines) at any point. It's important to realize that the metric tensor, while it allows to distinguish accelerating (curved) lines from the non-accelerating (straight) lines, can't distinguish "moving objects" from "objects at rest". This is the principle of relativity underlying both Einstein's famous theories but in this general form, it was true already in Newton's mechanics - and realized by Galileo himself.
A: The answers that have already been posted are correct, but @kakemonsteret raises a followup question in the comments that's worth addressing:

Lets say you are spinning somewhere in
  outer space, can you know you are
  spinning, ie can you rule out that the
  forces you feel are not caused by a
  mass distribution somewhere ?

This question is getting at some ideas about Mach's principle and its relation to general relativity, which is a somewhat complex subject. But there is a well-known effect in general relativity that bears directly on this question: the Lense-Thirring effect. 
Imagine a large spinning spherical massive shell. The local inertial reference frames inside the shell will be "dragged" around by the rotating mass, so that they rotate with respect to the "fixed stars" (i.e., the inertial reference frames far outside the shell). So if you lived inside this shell, and felt like you weren't rotating, you would "really" be rotating relative to the fixed stars. If you then started turning the opposite way at just the right rate, you could make it so that you weren't "really" rotating relative to the fixed stars, but you felt like you were.
I put scare quotes aroung the word "really" there for a reason: in general relativity, the most natural meaning to ascribe to the phrase "really rotating" is "rotating with respect to your local inertial frame" -- that is, if you feel like you're rotating (or if your Newton's bucket indicates you're rotating), then you are. But if you define "really rotating" to mean rotating with respect to very distant inertial objects, then yes, you can feel like you're rotating, even when you're not "really rotating," due to being surrounded by lots of spinning mass.
Needless to say (I presume), this is all very much in-principle stuff: the frame-dragging effect is very small in practice.
A: The reason that the Bucket knows that it is spinning is that the Universe has a horizon in much the same way that the Earth has a horizon.  The Earth's Horizon is curved line that is there not only because of Perspective Geometry, but also because the Earth is curved. Because the Earth has a two dimensional surface the height tilts back away from the observer, so no matter how tall the height, all heights will tend to an line, which we call the Horizon.
   The surface of the Universe has a three dimensional surface, the height is called "time" and the curvature of the Universe causes all lengths of time to disappear and become a "red-shift" that we call the CMB.  The CMB is not really the "Event Horizon", nor is it the start of the "Big Bang".  It may also be those things, but that is not the importance of the CMB.
   The Bucket knows it is rotating, because the Universe has a definite Up and Down, or Inside and Outside (which is probably a more accurate description).  This is a very ingenius solution to the problem, and proves that the current theory is wrong, and gives a reason for Quantum Mechanics as well. The other type of spin is also the direction showing that the Universe has a definite outside, but it is a second dimension of time--that dimension of time is set on a Negatively Curved surface, unlike the one we are used to, which from the argument above is set on a Positively Curved surface (which gives the CMB).
    The negatively curved surface gives rise to Non-Laplacian statistics, since any given point can come from an infinite number of timelines, whereas the Positively curved surface gives rise to a time that is eerily similar to classical Electrodynamics.
    There is probably only one surface, which has time "vectors" on both sides, one side is Positively curved the other Negatively curved. This is possible in a curved three space.
