What is intrinsic curvature?

This is a difficult conceptually. I agree. We currently have no evidence that suggests our 4-dimensional universe is embedded in some higher dimensional space.

For a sphere embedded in a 3-dimensional space, you can elect to use intrinsic or extrinsic geometry. Both will give you the same measurements.

But in our universe, there is not higher-dimensional embedding space we can refer to. So we are stuck with intrinsic geometry. How I think about it is this: there is really no reason that it must be true that, for example, a triangle has interior angles summing to $180^o$ or that the dot product of basis vectors is zero. Any of these geometric elements that are postulates in Euclidean geometry aren't inherent truths about the Universe. They're just what we see in our everyday experience. That is, they're in a sense empirically discovered.

So how do you discover intrinsic geometry empirically? You measure angles, you measure dot products and you see what the values are. If those values are what you'd get with flat space, you're in a flat space. If they're what you'd get in curved space, well, you're in a curved space. You can consider this the definition of a curved space. You don't have to envision space bending into some other space. Just that in our space, we measure dot products of basis vectors to have some non-zero value.

In response to your edit:

Specifically and by definition what it means for a space to be intrinsically curved --- like all these answers say --- is that when you take geometric measurements they don't come out the way Euclidean geometry predicts.

We call it "curvature" because it works exactly like curvature. Angles and distances measured are exactly what they would be if the space was curved. We don't assume an embedding space because we don't need to to get the right answers. So why add something to the theory that cannot be observed?

Intrinsic and extrinsic curvature are connected in that they both make the same predictions. Just how you do the math is a bit different. If you don't exist in the embedding space, then you can't use the tools of extrinsic curvature to take measurements. You have no choice but to measure things intrinsically.

Unless you can observe the embedding space, then no, you cannot deduce that you exist embedded in a higher space. That's an assumption that cannot be tested.

Extrinsic curvature refers to embedding a space in a higher number of dimensions. Intrinsic curvature refers to the geometrical theorems which can be proven within the space, without reference to anything outside. For example the angles of a triangle may not add to $180^\circ$. The two definitions of curvature are distinct. A sphere has both intrinsic and extrinsic curvature, but a cylinder can be made by rolling a flat piece of paper, without distortion of geometrical shapes like triangles; it is extrinsically curved and intrinsically flat.

Spacetime (and space) has intrinsic curvature, but no extrinsic curvature because there is no exterior space to look at it from. This means that maps of large regions cannot be drawn without distortion of the map. The easiest way to see that this is true is to recognise the daily fact that clocks on GPS satellites do not keep time with identical clocks on Earth. Since the laws of physics on satellites are the same as the laws on Earth, the speed of light is the same, and consequently there must be an apparent difference in the length of the metre, when viewed from Earth. As a result, the circumference of the orbit of the satellite is not equal to $2\pi R$ as it would be in a flat geometry.

I learnt that a sphere has intrinsic curvature, that is a 2d creature on a 2d sphere can still find out that a sphere is curved. But I dont understand what that means.

The way that you determine curvature of a sphere using only measurements in the 2D surface of the sphere is by finding things that violate the rules of normal flat Euclidean geometry. For example:

In a flat space the sum of the interior angles of a triangle is $180^{\circ}$. But on a sphere you can draw a triangle that starts at the equator, goes due north to the North Pole, turns $90^{\circ}$ goes due south to the equator, turns $90^{\circ}$, and goes due west to the starting point. This triangle has $270^{\circ}$ interior angles.

Similarly, at the equator two nearby lines pointing due north are parallel. But as you follow each line due north the distance decreases, the angle changes, and the lines eventually intersect.

Neither of these examples are possible for a flat space, so even a 2D being confined to the sphere could determine that the space was not flat, without either needing or obtaining any evidence for or against a higher dimensional flat space.

Since our spacetime is curved, is it embedded in more than 4 dimensions?

We simply don’t know the answer to this. We have no evidence to support the idea nor any evidence to rule it out. Whether it is there or not, it seems to be unnecessary for describing physics.