Renewable resources and energy storage systems integrated into microgrids are crucial in attaining sustainable energy consumption and energy cost savings. This study conducts an in-depth analysis of diverse storage systems within multi-energy microgrids, including natural gas and electricity subsystems, with a comprehensive focus on techno-economic considerations. To achieve this objective, a methodology is developed, comprising an optimization model that facilitates the determination of optimal storage system locations within microgrids. The model considers various factors, such as operating and emission costs of both gas and electricity subsystems, and incorporates a sensitivity analysis to calculate the investment and maintenance costs associated with the storage systems. Due to the incorporation of voltage and current relations in the electricity subsystem as well as gas pressure and flow considerations in the natural gas subsystem, the developed model is classified as a mixed-integer nonlinear programming model. To address the inherent complexity in solving, a decomposition approach based on Outer Approximation/Equality Relaxation/Augmented Penalty is developed. This study offers scientific insights into the costs of energy storage systems, potential operational cost savings, and technical considerations of microgrid operation. The results of the developed decomposition approach demonstrate significant advantages, including reduced solving time and a decreased number of iterations.