Rubber boots stick in mud for the same reason a suction cup sticks to a smooth surface - the atmosphere holds them down. A suction cup seals to a surface, keeping air from going in and out. There are more air molecules colliding with the top than with the bottom so the air pressure isn't balanced. You may have noticed that a suction cup sticks better when you flatten it and get most of the air out. When this happens most of the air molecules colliding with it are exerting a force in the downward direction.
When boots sink into mud the force they exert on the mud pushes air out and the mud conforms to bottom of the boot. Mud is a suspension that has the property of flowing like liquid, but resisting force like a solid. So the boots become like suction cups stuck to a solid-like surface of their exact shape. When you lift your foot upward, you're working against the pressure of the atmosphere.