Would "Energy Vault" gravity battery work in water? To be more specific, will one block lowered into water release the same amount of energy as in air?

 A: It would work, but buoyancy would reduce the effective density of the masses by 1 g/cm^3. So, for iron blocks, you'd need ~15% more mass or height for the same storage. For less dense materials, the effect is relatively larger.
A: Short answer: No, stacking bricks underwater will store less energy than stacking them in air.
Here are two ways of looking at the problem that lead to the same conclusion.
First, forces.
When lowering a brick it can do work for you for example to run a generator.  The amount of work it can do is equal to the force it applies multiplied by the distance through which it's lowered.  In air, when lowered at at steady speed the the force the brick applies, which is tension in the cable, is equal to the force of gravity on the brick.  When lowering a brick under water once again forces on the brick are balanced but now there is also an upwards buoyant force on the brick.  This makes the tension force less and so less work can be done.
Second, potential energy.
Another way of looking at this system considering what happens to the energy of the gravitational potential of the brick.  As the brick is lowered it loses gravitational potential energy.  This energy is converted to some other form of energy, for example to electrical energy via a generator.  At first glace it would seem that lowering a brick in air, or under water would produce the change in gravitational potential energy for the brick and indeed it does but...  The brick is not the only thing changing it height in this situation.  As the brick is lowered an equal volume of water rise the same distance to replace it.  This water gains gravitational potential energy but not as much as the brick loses because its mass is smaller.  The amount of useful energy you get from lowering the brick is equal to the energy lost by the brick minus the energy gained by the water.
So either way you look at it the system have a smaller energy storage capacity under water that it does on land.
A: Imagine a gravity battery in a mine shaft. Now imagine you establish the equivalent of a well full of water on one side of the shaft. Send a heavy but bouyant object down the air shaft. Then expend a relatively small amount of energy to transfer the object into the water shaft. It uses gravity on the way down and bouyancy on the way up.
