Big balloon tethered to sea floor. Pump air in when you've got spare energy, hydrostatic pressure forces air back out when needed. The neat bit is that the air pressure doesn't tail off as the bag empties. Site near offshore windfarms and you don't need much more infrastructure.
The main issue as I understand it is that you lose a lot of energy to heat if you just pump air straight in. To be efficient you need to chill the compressed air down to water temperature and store the heat before you pump the air underwater. Then add the heat back to the air when you release it from the balloon. This is all doable, but with all those heat pumps it's not quite as simple/cheap as it might seem.
