Coalbed methane (CBM) resources cannot be efficiently explored and exploited without a robust understanding of the permeability of fracture-size heterogeneities in coal. In this study, two sister coal samples were imparted with pre-developed cleat and connected fractures, and the permeability of the coal samples was measured under different conditions of controlled confining and gas pressures. Furthermore, the implications of the results for CBM exploration and exploitation were discussed. The permeability of coal with cleat development ranged from 0.001–0.01 mD, indicating ultra-low permeability coal. The gas migration in this coal changed from a linear flow to a non-linear flow, with the increase in gas pressure (>1 MPa). Thus, the permeability of the coal initially increased and then decreased. However, the Klinkenberg effect does not exist in this ultralow-permeability coal. For the coal sample with connected fracture, permeability ranged from 0.1–10 mD, which is larger by hundred orders of magnitude than that of the sample with cleat. For this coal, with a decrease in gas pressure (<1 MPa), the Klinkenberg effect significantly increased the permeability of the coal. With an increase in the applied confining pressure, both the Klinkenberg coefficient and permeability of the coal presented a decreasing trend. It is suggested that field fracture investigation is a prerequisite and indispensable step for successful CBM production. The coal beds that cleat network is well conductive to the connected fracture can be an improved target area for CBM production. During CBM production, a variety of flow regimes are available owing to the decrease in CBM reservoir pressure. In particular, under the low CBM reservoir pressure and low in situ geo-stress conditions, the gas migration in the CBM reservoir with connected facture development exhibits remarkable free-molecular flow. Thus, the reservoir permeability and predicted CBM production will be enhanced.