Form of Energy in Compressed Gas

The internal energy $U$ of a given mass of an ideal gas depends only its temperature. It is the same whether the gas is compressed or not. What the compressed gas has is more of is free energy. This is defined as $F=U-TS$ where $T$ is the temperature and $S$ is the entropy $$ S= NR(ln V + constant). $$ Here $N$ is the number of moles of gas present and $R=8.31$ J K$^{-1}$ mol$^{-1}$ is the gas constant. The enrotropy of the compressed gas is smaller by $NRln( V_{smaller}/V_{original})$ and so the compressed gas has more free energy than the uncompressed. It is the free energy that is available to do work, and is the approprite analogue of the energy stored in a spring.

So the anwer to your question is that the best characterization of the stored energy is that it is entropic.