Carbon capture and storage (CCS) systems can provide sufficient carbon raw materials for power-to-gas (P2G) systems to reduce the carbon emission of traditional coal-fired units, which helps to achieve low-carbon dispatch of integrated energy systems (IESs). In this study, an extended carbon-emission flow model that integrates CCS-P2G coordinated operation and low-carbon characteristics of an energy storage system (ESS) is proposed. On the energy supply side, the coupling relationship between CCS and P2G systems is established to realize the low-carbon economic operation of P2G systems. On the energy storage side, the concept of “ state of carbon” is introduced to describe the carbon emission characteristics of the ESS to exploit the potential of coordinated low-carbon dispatch in terms of both energy production and storage. In addition, a low-carbon economic dispatch model that considers multiple uncertainties, including wind power output, electricity price, and load demands, is established. To solve the model efficiently, a parallel multidimensional approximate dynamic programming algorithm is adopted, while the solution efficiency is significantly improved over that of stochastic optimization without losing solution accuracy under a multilayer parallel loop nesting framework. The low-carbon economic dispatch method of IESs is composed of the extended carbon emission flow model, low-carbon economic dispatch model, and the parallel multidimensional approximate dynamic programming algorithm. The effectiveness of the proposed method is verified on E14-H6-G6 and E57-H12-G12 systems.