The concept of energy is a rather mysterious one. Feynman's explanation is probably one of the most beautiful, simple, and clear I've seen so far, you should try and check it for a good understanding.
The main point of the answer to your question, though, is that we like to define energy as being always related to the force used for moving objects, not for holding them in place. To keep an object still doesn't change its energy, although force may be needed: you can thus think of energy as a measure of an object's ability to interact with other objects, changing their state of motion, for example by colliding with them or by pulling or pushing them around. Holding an object in place maintains its potential for interaction (energy), it doesn't change it. If you release the object by removing the table, you can turn that potential for interaction into real interaction, for example by tying your object to a pendulum clock and have it move the dials while losing height (by the way, this is sometimes called a gravity battery).
A change in energy is called work, so for those forces which cause no change in an object's energy we say that they do no work. They are often called ideal constraint forces, so the table in this context would make for an ideal constraint.
The main reason all this stuff sounds counterintuitive is that we as animals consume energy even for static holds, but that is due to the fact that our muscles work by continual micro-contractions, not by a single hold. A static hold is never truly static for our muscles, rather is a very fast cycle of pull-and-release type oscillations (you might be aware of the actual mechanism) which actually does work at a microscopic level (it takes the energy from ATP bonds), though not at a macroscopic one. A table doesn't experience this kind of fatigue, since atomic repulsion is rather static in nature.
EDIT to address further question:
Increasing the weight will make the table bend and squeeze. Its atoms will then be at a higher energy state because of the stretching and squeezing of their bonds (which can be reasonably accurately be thought of as acting like microscopical springs). This increase of energy will come at the expense of the energy of the object, which will fall a little distance by bending the table downwards. What we expect is that the bending will eventually stop. This can be explained in terms of energy by the fact that, as you bend the table, the energy required to further bend it increases. You reach a point where lowering the object yields less energy than is required to bend the table, so the descent stops.
If no energy is dispersed in the process, lifting the weight will let the table go back to its initial, straight position. If there is energy dispersion (bonds are broken), then the table won't be able to get back to its initial position. If the dispersion is slow, the table will get saggy. If it is fast, the table will crack and break.
Note that all this is regardless of the table's height: unless the object is tied to the ground with some sort of spring, raising the table and the object together (like carrying them to the second floor) doesn't stress the table more. Otherwise we couldn't have desks in skyscrapers.