Exactly constrained means that a moving part on a machine has parts that locate it in X, Y, Z, Theta, Rho, and Phi. Over constrained means that one or more of the directions and rotations have two or more parts fighting to control them.
A common example of this is an axis running on two linear bearings. To make this simple, I'll talk through it in terms of two ground rods with a total of four tubular linear bearings running on them and a lead screw. Lets say X is the direction parallel to the rods. The X direction is controlled by the lead screw; easy. The Y and Z directions are controlled by the linear bearings. Rotation around the X axis is controlled by the linear bearings, as are rotations around the Y and Z axes.
There are two big over-constraints. The first is that the pair of linear bearings on a ground rod MUST be co-axial to be able to move. This is typically pretty easy to do, as you can often stick them on the rod and then screw them in place. A lot of linear bearings include some facility to provide a small rotation to self-align.
The tough one is the two ground rods. If they are not parallel, then the motion will jam. Getting them onto a common mounting plane helps alignment a lot, but you still have to get the two parallel (within the flex/slop of the system) to get motion to work. We often solve this by using a flat surface to mount the ground rod ends and then doing the trick where you go to one end, tighten the mounts some, go to the other end and tighten a bit, rinse and repeat...
As for the rotations, lets think about X first. If the table rotates around the lead screw, nothing happens (other than a little motion). Thus, the lead screw doesn't control this rotation. If we consider the right hand ground rod to be the master one, we can imagine rotating the table around it. This rotation is prevented by the TWO bearings on the other ground rod; this means that its over-constrained, and that we have to do some sort of special alignment to get it to work. Y and Z have an even higher degree of over-constraint; they each have 2 or 3 extra bearings fighting for control plus the lead screw is going to resist rotation around Y and Z (and bind up).
If you go to a total of three linear bushings, things get quite a bit happier. Think of "three points define a plane". Using a fork/slot bearing as the singleton is the best choice, or putting the singleton linear bearing IN a tight slot. One or both bearings on a common shaft need a spherical housing (ideally something you can clamp after installation). In a perfect system, the coupling between the lead screw and the table would have a couple of flexures so that the nut can seek its own happy spot. Set up this way, X is only controlled by the lead screw. Rotation about X is controlled ONLY by the fork bearing.
Y is controlled by the bearing pair (remember the fork is pointed in the Y direction). Rotation around Y is also controlled by the bearing pair; the fork won't contribute any significant rotation resistance as its short relative to the pair. Finally, Z is set by the three table bearings. Rotation around Z is just like Y; the bearing pair.
After I funded the Cobblebot printer, I found out the hard way that they TOTALLY didn't understand this stuff. They had a quadruple bearing group running in grooves on EACH of the four posts. Thus, the darn posts had to be totally parallel for the Z to move at all! And, the two screws had to parallel also. Further, the motors were on the bottom, so the most critical position (starting) was the one most likely to bind up! The Y axis had two bearing quads. Again, requiring two linear rails to be perfectly parallel to each other. X was the only one that would run reliably.
Sorry for the long blather! Its a topic dear to my heart, and one that I spent a LOT of time on to get my printer working right.