Shale matrix permeability is an important indicator for evaluating gas transport and production. However, the effects of pore connectivity and water saturation on the matrix permeability in deep gas shales have not been adequately studied. In this study, the permeability of deep shales in the Yichang area of the Middle Yangtze was characterized using three methods. These included the determination of apparent permeability in different directions via pulse-decay, also matrix permeability obtained via the Gas Research Institute method, and the connected pore network permeability via the mercury injection capillary pressure technique. The results revealed a significant difference between the horizontal and vertical permeability of deep shales. The smaller the size of the multiple connected pore network, the larger was the effective tortuosity and the lower the permeability. Comparison of the three permeabilities and combined microscopic observations revealed that microfractures and laminae were the dominant gas transport channels. Importantly, the matrix permeability decreased exponentially with increasing water saturation, with water vapor adsorption experiments revealing that water occupation of pores and pore-throat spaces smaller than 10 nm in diameter was the main reason for this decrease in matrix permeability. Collectively, proposed method of evaluating effective permeability with an index for shale gas reservoirs is significant for sweet spot selection and production prediction of shale gas reservoirs around the globe.