Graphene-based nanomaterials (GNM) are plausible candidates for cancer therapeutics and drug delivery systems. Pure graphene and graphene oxide nanoparticles, as well as graphene quantum dots and graphene nanofibers, were all able to trigger autophagy in cancer cells through both transcriptional and post-transcriptional mechanisms involving oxidative/endoplasmic reticulum stress, AMP-activated protein kinase, mechanistic target of rapamycin, mitogen-activated protein kinase, and Toll-like receptor signaling. This was often coupled with lysosomal dysfunction and subsequent blockade of autophagic flux, which additionally increased the accumulation of autophagy mediators that participated in apoptotic, necrotic, or necroptotic death of cancer cells and influenced the immune response against the tumor. In this review, we analyze molecular mechanisms and structure–activity relationships of GNM-mediated autophagy modulation, its consequences for cancer cell survival/death and anti-tumor immune response, and the possible implications for the use of GNM in cancer therapy.