Is the pressure of air or water on an object beneath (pushing upward) and above (pushing it downward) it equal? I once read that, even if a stone is lying at the bottom of the ocean, the pressure beneath the stone is still equal to the pressure of the water above it. 
But that sounds a bit strange as there is much more water above it than beneath. Secondly gravity is pulling the water downwards and not upwards. So what causes this the be (almost?) equal?
I suppose that the same is for objects in the air. When a table of  $1 m^2$ undergoes a pressure of 10.000 kg above it, the same pressure will push the table upwards, so finally only gravity is pulling the mass of the table to the Earth. But how is this possible?
 A: The key to answering your question is to understand that pressure at any depth in a fluid (liquid or gas) causes the same force in all directions.   There are several "levels" of understanding this.
The most intuitive way to see it is to imagine sitting on a trash bag full of water.   Of course that increases the pressure the water.    But even though your weight is pushing downward, water will squirt out anywhere you poke a hole in the bag, including the top, bottom and sides.
But to apply this idea clearly to the bottom of a rock in the water, or the bottom of the table, we need a deeper understanding.    Pressure is not force.   Pressure causes force (and force causes pressure).   Pressure itself is the volume concentration of the energy of the particles (atoms and molecules) in the fluid.   It's the energy per unit of volume.   In a gas, that energy is mainly kinetic--associated with the mass and speed of the particles.   In a liquid, the energy is mainly potential-associated with the particles being pressed a tiny bit closer together against enormous restorative forces, like extremely stiff little springs.
When an object is placed in either a gas or a liquid, the energy of the particles causes force on the surfaces of the object.  In a gas the force is mainly the effect of the many, many virtually simultaneous collective collisions of the fluid particles against the surface during any instant of time.  In a liquid, the force is the effect of the many, many little "compressed springs" constantly pushing against each other and against the surface, like the famous video footage of a crowd of soccer fans crushing each other against a fence.  
In the atmosphere the cumulative weight of the air above compresses the air more and more with increasing depth, so there are more and more particles per unit volume and therefore more energy per unit volume.   Near the surface of the Earth the particles are colliding with the top of the table and the bottom of the table at an equal rate.   If you put a book on the table, there will be only a tiny volume of air under the book, but the energy per unit volume-the pressure under the book, will be the same.
The weight of the ocean does not compress the water much at all--it's almost incompressible.  The tiny bit of compression that does occur does not increase the number of particles per unit volume very much, but it does increase the force between them a lot.  So again, the volume of water under the rock may be small, but the energy per unit volume is the same.
A: Below I illustrated your 'a stone is lying at the bottom of the ocean' problem.
It relies on two formulae:
The pressure on an object submerged in a static fluid is the product of the fluid's density, the gravitational acceleration it experiences, and the depth of the object, or the height of the fluid above it.
The formula:
$$
P = {ρ \times g \times h}
$$ 
Where ρ is the density of the fluid, g is the gravitational acceleration (on Earth = 9.81 m/s2), and h is the height of the fluid above the object.
The pressure on a surface is given the formula:
$$
P = {F \over A}
$$ 
Where F is the normal of the force applied and A is the area of the surface on contact.

A: 
I once read that, even if a stone is lying at the bottom of the ocean, the pressure beneath the stone is still equal to the pressure of the water above it.
But that sounds a bit strange as there is much more water above it than beneath.

The pressure must be equal. But noone said water pressure. The water pushes from the top just as much as the seabed pushes from the bottom. If the water pushed more downwards, than the seabed pushed upwards, then the stone would accelerate downwards - it doesn't, so there must be equilibrium.
Actually, the upwards push from the seabed is a bit bigger than the water pressure - because the seabed must hold up against both water pressure and the stone's weight. You can say that it holds both the stone and the vertical column of water above it up.
Remember that pressure is just force per area. Newton's 1st law holds.

Secondly gravity is pulling the water downwards and not upwards. So what causes this the be (almost?) equal?

Gravity causes the water pressure from above, yes. A normal force causes the seabed pressure upwards. It is often called a normal pressure in this context in mechanics.

I suppose that the same is for objects in the air. When a table of $1m^2$ undergoes a pressure of 10.000 kg above it, the same pressure will push the table upwards, so finally only gravity is pulling the mass of the table to the Earth. But how is this possible?

Indeed the same is the case in air. Newton's 1st law still holds. Things that do not move must be held up with the same force (and pressure) that pushes down.
And again, the ground's upwards pressure will not be equal to the 10.000 kg pushing downwards, it will actually be a bit bigger - because it must hold back against the 10.000 kg and the table's own weight.
Objects like this therefore do feel a bigger pressure on their bottom than on their top. But especially in water this pressure difference is small, because the water's own weight is large and has the biggest influence. Therefore it is often said that the water pressure is the same all around submerged objects, which assumes that they are not too heavy and not too large.
