gravity - What is spacetime 'made' of?

General relativity is often explained as saying spacetime is curved by gravity, what does this mean?

It means that general relativity can be formulated in a way in which its mathematics have a very direct analogue to differential geometry on a curved four-dimensional manifold. In other words, the way test particles would behave under the influence of only gravitational forces is exactly how they would behave if moving freely on a curved four-dimensional manifold. The mathematics have a direct correspondence: nothing more, nothing less.

Electromagnetism has a description in which the electromagnetic field strength is the curvature of a connection on a line bundle. I realize that this statement is very cryptic to someone who hasn't studied gauge theory, but it's important to realize that an essentially geometric description is not special to gravity. What's special to gravity is that it couples to all stress-energy-momentum equally, and gravitational freefall of a test particle is completely independently of composition.

Because of this universality, it is possible to interpret the properties of the gravitational field as properties of spacetime, i.e. as property of the arena on which everything else happens. We don't have to do so, and indeed there are some presentations of general relativity (e.g., Weinberg's) in which the geometric interpretation is relegated to an unimportant side note, but we can--and geometry is how general relativity was originally developed.

How could we perceive a curve in spacetime when there is no external "straight" reference frame for instance?

We could measure it.

As a conceptually (but not practically) simple way to do so, we could set up a small ball consisting of initially comoving test particles. With no curvature of the gravitational field, every such ball would keep the same shape and volume because they're all the test particles are moving in the same direction with the same speed. But if the gravitational field has Ricci curvature, the volume of the ball would either start shrinking or expanding. Similarly, changes in the shape of the ball would give information about Weyl curvature.

This is the same kind of answer as in the case of electromagnetism: the field strength is also a kind of curvature (though not of spacetime), but how do we perceive it? Well, we could measure it by seeing how test charges behave.