Rigid bind is where an object's skin is only "bent" on the edges when you move the skeleton. Smooth bind makes the skin near the joints of the skeleton, well, smooth. Go to Bind Skin and click "help" then "help on rigid bind." You should be given a window that explains everything about rigid bind. Do the same for Smooth.

*edit* - Well, actually, rigid bind is more like keeping the objects geometry solid, while smooth bind inables the skin to become more flexible. Take a cube for instance. Select one face, then choose EditPolygons>Extrude Face. Pull the manipulator out a little and you have an extruded face. Press the G key and pull some more. Do this several times until you have about 5 extrusions. (you can also choose the options box for Extrude face and select a number of divisions) Anyway, create a 5-jointed skeletion and place it inside the extruded cube. Select the Skeleton, then shift select the Cube. Choose Skin>Bind>Smooth Bind. Select one of the middle joints, so you can easily see the effect and rotate it around. Undo your actions after you've seen what the results are up to the point before you binded the skin to the skeleton. Now, select the first joint of the skeleton, then shift select the cube. Choose Rigid bind this time. Select the root joint and rotate it. Notice how the geometry moves as a whole? If you do not rotate the first joint you selected, (you select the second or third or forth joint) The geometry will not move.

If you smooth bind an object, basically, the skin will be able to move anywhere there is a joint.