In general relativity, a space (or more precisely, a spacetime) is said to be curved because Euclidian geometry does not hold in it. It is not possible to visualize a curved 3D space, so I'll use 2D for example. A 2D Euclidian world is the surface of a plane. If you measure the circumference of a circle with radius r, you'll get 2πr. This is not generally the case in a non-Euclidian world, such as a curved surface. Imagine a 2D person living on the surface of the Earth. It is a 2D world, so there is no notion of "above" or "below" the ground for him. If he takes a rope of length r, fixing one end at the North pole and sweeping a circle by the other end, the circumference of the circle will be less than 2πr. There is nothing wrong for him that the ratio between the circumference and the radius is not 2*3.14, since it is the way his world works.
General relativity says that a mass will curve the space, so Euclidian geometry will not be valid near a massive object. You can visualize a 2D black hole with a picture like this:
(Courtesy of Jeffery F. Lockwood)
Remember that there is no notion of up or down for the person in the 2D world. The up-down axis is just used here to stretch out the distance to and from the black hole, compared to the sizes of the circumferences of the circles around it. Note that the slope of the surface around the center is nearly vertical, meaning that even if a traveler travels a long distance toward the black hole, he barely gets closer to smaller circumferences. A practical consequence is that, as viewed from far away, the traveler never quite reaches the edge of black hole (the "horizon" at the Schwarzschild radius).
So the answer to your question is: the spacetime itself is curved. At least so far as we currently understand, there is no "medium" of space that interacts with mass. Since it is hard to visualize the concept, the 2D "fabric" shown above is usually used for illustration.
(published on 05/24/12)