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.