Klinkenberg effect is an important phenomenon for gas flow in low permeability reservoirs, and its influence increases with the reduction of gas pressure. Unlike conventional gas reservoirs, coal seam is unique with its high compressibility and sorption-induced-swelling features. During the coalbed methane (CBM) recovery process, coal cleat width varies due to the net effect of effective stress and coal matrix shrinkage, thus the Klinkenberg coefficient cannot be treated as a constant like rock reservoirs. A brief review of previous studies shows that the influence of coal seam characteristics on Klinkenberg effect was ignored by other researchers. By using the bundled matchstick conceptual model of coal, two improved models are proposed in this paper, one is under constant effective stress and the other is under reservoir condition. The former shows that the proportion of permeability change due to Klinkenberg effect is greater than the result from original model, and the Klinkenberg coefficient varies substantially albeit the influence of effective stress is eliminated. The latter links apparent permeability and coal porosity together, and the results show good agreement with field data, especially when the gas pressure is relative low. It can be concluded that apparent permeability model is crucial for explicit prediction of gas permeability changes during CBM recovery process, which may be underestimated without due consideration of Klinkenberg effect. The development of the improved apparent permeability models has significant value in the accurate prediction of CBM production as a result of permeability changes.