Gimbal lock occurs when using Euler angles for your rotations. The problem is that the evaluation of the axis of rotations is done in a set order and independent of each other.The order of rotation is usually, Y, X & Z but isn't necessarily so.
This is one of the decent explanations on the subject that I know of:
http://www.sjbaker.org/steve/omniv/eulers_are_evil.html
While quaternions are often cited as the best solution to the above problem, you can actually stick to Euler angles if you aren't doing anything fancy. For eg, a workaround which is often used when implementing an FPS camera is to restrict pitch and roll to +/- 89 degrees, while there is no restriction on the yaw.