> Not sure how natural gas is stored though.

Mostly stored underground, but it's also shipped and stored in a liquefied state at -162C. Propane is one of the components of natural gas, so I would think any facility that is able to store natural gas should be able to store propane easily.