The system has an air reservoir at the bottom of deep water, with a compressed air pipe from the compressor/turbine set at the surface connected to its top. The basic system would have the reservoir wide open at the bottom. This fine for short-term energy storage, when air going into solution isn’t really a problem – no worse than evaporation from the upper reservoir of a pumped hydro system.
You could have a barrier floating on the surface of the water in the tank, which would be a cylinder with a vertical axis. The barrier need not be a tight fit in the cylinder: you are trying to reduce the rate of dissolution, not necessarily to prevent it entirely. Even at high pressures, air does not dissolve rapidly in water, and the smaller the surface area of water exposed to the air, the less will dissolve in a given period. Also, the longer the narrow part of the path from the air to the bulk of the water, the more slowly the air will dissolve because it can only dissolve as fast as the air that’s already dissolved diffuses away – so the barrier should have a fairly wide “skirt.”
The barrier would have to be a very loose fit, or it would be very susceptible to fouling.
You could also have a closed bottom with a pipe (as shown) to let the water in and out, wide enough for fouling not to be an issue over the life of the system, but much narrower than the diameter of the reservoir, to reduce the rate of loss of air. Air in solution would have to diffuse along the pipe to escape. The pipe in the diagram has two double bends, so that it neither sucks up debris from the bottom, nor does it collect any debris falling from above.
(In practice I suspect this is unnecessary, with a wide enough pipe and a big enough clearance between the skirt and the cylinder, which would almost certainly still keep loss of air by solution and diffusion quite small enough. )
You could have a pipe from the bottom to take the water to the surface, where you could retain the water in a closed reservoir, to prevent fouling organisms getting into the system. This doubles the number of reservoirs, but they’re not high pressure reservoirs like those required for conventional compressed air systems. The upper reservoir would have a (filtered) air vent at the top.
Finally, you could have a valve in the return pipe, which you would close whenever the system is neither charging nor discharging. This would prevent dissolved air escaping via the retention reservoir. (If the valve is at the top of the pipe, as shown, after a very long storage time, there could be one pipeful of air lost! The advantage is that the valve is more accessible for maintenance.)
Low cost, long expectation of life in (sea)water, and adequate strength are the main criteria. My guess is that glass-fibre reinforced concrete  would be a good choice, but I don’t know whether something else might be better. Weight isn’t an issue in service – in fact holding the vessel down when it’s full of air is more of an issue than holding it up when it’s empty! (But isn't any harder in 1000m of water than in 100m.) However, weight is a possible issue during construction.
There are many ships (supertankers, container ships, cruise liners) of 200,000 tonnes plus . A vessel of that displacement (that is, the same size as the underwater part of the ship) at a depth of 1,000m would store ~2.5 GWh. At 200m it would store ~350 MWh. These vessels would be very much cheaper than those ships – much simpler, and without the above-water part.
There’s no magic about the 200,000 tonnes size; the vessels could be very much larger or very much smaller than that.
Where there isn’t a retention vessel at the surface, the pump-turbine-generator unit would probably be supported like a deep-sea oil rig, with floats well below low tide wave trough level, legs from them to support the platform well above high tide wave peak level, and anchor cables in permanent tension. This probably wouldn’t be practical for a system with a retention vessel, which would have to float up and down with the tide, most probably with the pump-turbine-generator unit attached to it – unless the system was close enough to shore that the pump-turbine-generator unit, and possibly even the retention vessel, could be ashore.
The same technology could also be used for storing other gases, such as hydrogen or methane. You might still recover the compression energy as well as the fuel value of the gases. This might or might not be worthwhile, depending on the scale of the operation.
 See Diffusion Coefficients of Gases in Water.
 See Glass Fibre Reinforced Concrete. That article doesn’t mention coated glass fibres, only alkali-resistant ones. The concrete cladding on the external insulation on our house has coated glass fibre reinforcement! For more information see Strength properties of coated E-glass fibres in concrete (this is a .pdf and may be downloaded and saved rather than displayed, depending on your browser settings) and E-Glass Fibre.
 See List of largest ships by gross tonnage.