A gimbal is a pivoted support that allows you to rotate around one axis. Now it so happens that Euler rotations* work like a set of 3 gimbals attached to each other, one rotation builds upon the next (or previous/whole stack if your inclined to model it that way).
Image 1: Rotation is like a gimbal. Model using yxz rotation (z=blue, x= red and y=green) in a physical 3 axis gimbal structure.
A gimbal lock happens when you turn 2 or 3 of the successive gimbals and they align onto a plane. You succeed in erasing one direction since the angles both operate same same direction.
Image 2: Rotation direction lost because 2 of the rotations overlap.
The only way out is to unwind the structure. Although this is the lock, problems due to diminishing possibilities to turn start earlier than the lock itself.
A more in depth look at things
Now this is where most people stop thinking about the issue and move on with their life. They just conclude that Euler angles are somehow broken. This is also where a lot of misunderstandings happen so it's worth investigating the matter slightly further than what causes gimbal lock.
It is important to understand that this is only problematic if you interpolate in Euler angles**! In a real physical gimbal this is given - you have no other choice. In computer graphics you have many other choices, from normalized matrix, axis angle or quaternion interpolation. Gimbal lock has a much more dramatic implication to designing control systems than it has to 3d graphics. Which is why a mechanical engineer for example will have a very different take on gimbal locking.
You don't have to give up using Euler angles to get rid of gimbal locking, just stop interpolating values in Euler angles. Of course, this means that you can now no longer drive a rotation by doing direct manipulation of one of the channels. But as long as you key the 3 angles simultaneously you have no problems and you can internally convert your interpolation target to something that has less problems.
Using Euler angles is just simply more intuitive to think in most cases. And indeed Euler never claimed it was good for interpolating but just that it can model all possible space orientations. So Euler angles are just fine for setting orientations like they were meant to do. Also incidentally Euler angles have the benefit of being able to model multi turn rotations which will not happen sanely for the other representations.
Problems and how to circumvent them
The fact of the matter is that interpolating in Euler angle space is a bad idea, in general and affects you way before you come close to a true gimbal lock. For this reason NASA lunar orbiter would warn of gimbal lock when you come close to a 70-80 degree angle on a single gimbal's turn. So be aware that people do not necessarily talk of just the actual locking condition when they talk of a gimbal lock. Even worse some people blame all their rotation problems on gimbal locking.
Euler rotation is only safe if you rotate primarily one angle and shallow amounts on the other 2 rotations, which is quite common admittedly. This works fine for describing movement of a commercial airliner, a car etc. But not so well for a jet fighter or an acrobatics plane doing complex air maneuvers. What happens is the rotations start to interfere with each other and you get a weird wobble instead of moving straight from one position to the next.
To fix the wobble problem in shallow cases just swap the rotation order so that the big rotation gets applied on the other rotations. If you need to use more complex rotations then either switch over to other interpolation methods or add even more rotation links to your gimbal (which is a good stopgap measure for cases where you cannot do the switch in a timely manner).
* To be exact most of the time people do not actually use Euler angles but Tait–Bryan angles. Which are nearly the same thing only Euler insisted on repeating the same axis, not very important distinction but good to know if you ever speak to an academic.
** Oh well, if you use Euler–Lagrange equation it won't matter.
