In this paper, an ocean compressed air energy storage (OCAES) system is introduced as a utility scale energy storage option for electricity generated by wind, ocean currents, tides, and waves off the coast of North Carolina. Geographically, a location from 40km to 70km off the coast of Cape Hatteras is shown to be a good location for an OCAES system. Based on existing compressed air energy storage (CAES) system designs, a conceptual design of an OCAES system with thermal energy storage (TES) is presented. A simple thermodynamic analysis is presented for an adiabatic CAES system which shows that the overall efficiency is 65.9%. In addition, finite element simulations are presented which show the flow induced loads which will be experienced by OCAES air containers on the ocean floor. We discuss the fact that the combination of the buoyancy force and the flow induced lift forces (due to ocean currents) generates a periodic loading on the storage container and seabed, and how this presents engineering challenges related to the development of adequate anchoring systems. We also present a system, based on hydrolysis, which can be used for storing energy (in the form of oxygen and hydrogen gas) in containers on the ocean floor.