The ability of cancers to evade conventional treatments, such as chemotherapy and radiation therapy, has been attributed to a subpopulation of cancer stem cells (CSCs). CSCs are regulated by mechanisms similar to those that regulate normal stem cells (NSCs), including processes involving ubiquitination and deubiquitination enzymes (DUBs) that regulate the expression of various factors, such as Notch, Wnt, Sonic Hedgehog (Shh), and Hippo. In this review, we discuss the roles of various DUBs involved in the regulation of core stem cell transcription factors and CSC-related proteins that are implicated in the modulation of cellular processes and carcinogenesis. In addition, we discuss the various DUB inhibitors that have been designed to target processes relevant to cancer and CSC maintenance.