What is intrinsic curvature? What does it mean to say spacetime is curved?
My intuition suggests to me that whenever we have an $n$ dimensional curved object there is some m dimensional flat space in which the object is embedded, where $m>n$.
For example a sphere is curved but we understand that in relation to its embedding in $\mathbb{R}^3$.
But 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 don’t understand what that means. If such a creature knows that the sphere is curved, can it thus deduce that it must be in a 3d world?
Since our spacetime is curved, is it embedded in more than 4 dimensions? What exactly is intrinsic curvature? Is there an intuition for it? Is it connected to extrinsic curvature in any way?
 A: 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. 
A: 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. 
A: 
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. 
A: Our spacetime is intrinsically curved.
It is very important to understand the difference between extrinsic and intrinsic curvature.
Extrinsic curvature is when you are able to move to a higher dimension, and see that the lower dimension world is curved. You can see a lot those 2D rubber sheets, bent. Now imagine you can move outside (see it from outside the 2D), you are basically moving to a higher (in this case 3rd) dimension to see the 2D plane is curved. This is extrinsic curvature. Extrinsic curvature extends into a higher (spatial) dimension.
Intrinsic curvature is different, you cannot move to a higher dimension to see that your world is curved. To see this, imagine the same rubber sheet. Now we have grids on it. Instead of curving the rubber sheet itself, now curve the grids on the sheet without curving the sheet itself. Nothing special right? But you are viewing it from outside. But when you are on the sheet, living as a flatlander, you still think all the grids are straight. Whenever you move as a flatlander on the grids, you think you move straight. There is no way for you to know you are not moving straight. there is no higher dimension to move to see. This is counterintuitive. This is intrinsic curvature.


This type of curvature is what happens in general relativity. It's intrinsic not extrinsic. So to back to your question, you can't move behind the universe because there is no behind to move into. There are only the three spatial and one time dimensions - it's just that they are intrinsically curved.

Universe being flat and why we can't see or access the space "behind" our universe plane?
Now our universe is specifically intrinsically curved, because when you move in curved spacetime (geodesic), you are moving along a straight line. This intrinsic curvature is embedded into our spacetime. We cannot move to a higher spatial dimension to see this curvature. The only way for us to know there is intrinsic curvature is experiments like GR time dilation and gravitational lensing.
