Storing huge amounts of energy is easy: use pumps to add potential energy to water.

This isn't ultra efficient, but it's cheap and probably good enough. We have lots of experience with hydroelectric power.