The answer has to do with the form of static friction.
There are two types of friction, static and kinetic. Static friction is the type of friction that occurs when the bit of object that's touching the ground doesn't move (relative to the ground). Kinetic is the type that occurs when there is relative motion. Let's focus on static friction.
Consider a block sitting on a level, rough table. There will not be a frictional force. Why? Well, frictional forces are parallel to the surface (i.e., horizontal with the block on a rough table scenario). If there were a such horizontal force with nothing else acting on it horizontally, the block would be accelerating on its own. But we don't see this.
Now, magnitude of static friction forces can vary; it can range from zero up to some maximum value. The maximum value is $f_\text{max}=\mu_s N$, where $\mu_s$ is just a number that depends on the two materials in contact (e.g., wood block on plastic table), and $N$ is the upward normal force from the table. In order to start to move an object from rest, you have to exceed the magnitude of the static frictional force $\mu_s N$. When this starts to happen, the object will begin to move and kinetic friction will take over.
When you try to gently lift the block upward, but you don't actually let it leave contact with the table, the normal force $N$ decreases. This is because your upward force plus the normal force from the table has to counteract the downward gravitational force. If you apply a large upward force, the normal force doesn't have to be as large.
With this decrease in $N$ comes a decrease in $\mu_s N$, and hence a decrease in the maximum static frictional force. This means the force you need to apply in order to overcome $f_\text{max}$ is now less if you apply a small upward force to the block.
That's about it! Note that this is a very "macro" explanation that hinges on the form $f_\text{max}=\mu_s N$, which is just a very good experimental relationship. There are probably more microscopic explanations that could be more appealing to you.