Geological formations are suitable locations for CO2 sequestration, and among them, coals are excellent targets because of their nanoporous structure, which leads to a high gas adsorption capacity. The first part of this review summarizes the most important influencing factors on coal pore structure and resulting CO2 storage capacity. In the second part, the most commonly applied methods for pore structural characterization are introduced and discussed in the light of the challenges that arise from the complex and heterogeneous nature of coal microstructures. In general, it is recommended to use an array of complementary methods for microstructural characterization since pores in coals span over a wide size range from <1 nm to >1 mm. Coals furthermore show dual porosity (matrix pores and fractures) in most cases. Numerous factors may influence the occurrence of these pore types as well as the gas adsorption capacity, including formation temperature, coal rank, moisture content, swelling, maceral composition, ash content, stress state, type of gas, and gas pressure. All of these factors must be taken into account in order to optimize planned CO2 storage operations.