A novel carboxymethyl cellulose (CMC)-supported graphene oxide aerogel (CGOA) was fabricated from a cost-effective and abundant bituminous coal by a mild hydrothermal process and freeze-drying treatment. Such an aerogel has cross-linked graphene oxide layers supported by CMC, and therefore, displays high mechanical strength while having ultra-low density (8.257 mg·cm−3). The CGOA has a 3D interconnected porous structure, beneficial graphene framework defects and abundant oxygen-containing functional groups, which offer favorable diffusion channels and effective adsorption sites for the transport and adsorption of dye molecules. The adsorption performance of rhodamine B by an optimized CGOA shows a maximum monolayer adsorption capacity of 312.50 mg·g−1, as determined by Langmuir isotherm parameters. This CGOA exhibited a better adsorption efficiency (99.99%) in alkaline solution, and satisfactory stability (90.60%) after three cycles. In addition, adsorption experiments on various dyes have revealed that CGOA have better adsorption capacities for cationic dyes than anionic dyes.