Powders or cohesive granular materials are widely handled in industries. However, our understanding of the rheology of these materials is limited. Here, we provide a comprehensive analysis of the rheology of a cohesive granular medium, sheared in a normal-stress-imposed plane shear cell over a wide range of shear rate, employing numerical simulations. At high imposed shear rates, the flow is homogeneous, and the rheology is well described by the existing scaling laws, involving the inertial number and the “effective” cohesion number S. Mandal et al., Insights into the Rheology of Cohesive Granular Media, Proc. Natl. Acad. Sci. U.S.A. 117, 8366 (2020). However, at low imposed shear rates, the flow is inhomogeneous, exhibiting the coexistence of flowing and nonflowing regions in the material, popularly known as shear banding. We thoroughly analyze the crucial features of this shear-banded flow regime and discuss striking similarities between the shear banding for granular media and other complex fluids. We reveal that the occurrence of shear banding is related to the existence of a nonmonotonic intrinsic rheological curve and that increasing adhesion increases the nonmonotonicity and the tendency toward shear localization. A simple theoretical model based on a nonlocal rheological model coupled with a nonmonotonic flow curve is proposed and is shown to successfully reproduce all the key features of the shear banding observed in the numerical simulations. The results have important implications for the handling of powders in industries.