Parallax, in short, is the perceived difference in the position of an object when it is viewed along two different lines, such as when looking at an object from some distance with stereo vision. It's related to perspective projection in the sense that while the latter makes more distant objects look smaller, parallax makes more distant objects appear to be moving slower when, for example, one moves its head.
The 3D effect with parallax is thus established, even on a 2D surface, by having the objects that are supposed to be more distant move slower than those that are closer. This is an effect that is very useful with, for example, game backgrounds where you can make it appear that distant mountains are moving much slower than the characters walking in the foreground.
Hereby, we make use of layers. Essentially, the more layers we use, the smoother the effect is likely to be, though the perceived distance between layers and the amount of details in each layer are also important factors...