The characteristics of aerogel materials such as the low density and large surface area enable them to adsorb large amounts of substances, so they show great potential for application in industrial wastewater treatment. Herein, using a combination of completely environmentally friendly materials such as cellulose nanofibers (CNFs) extracted from the petioles of the nipa palm tree and graphene oxide (GO) fabricated by simple solvent evaporation, a composite aerogel was prepared by a freeze-drying method. The obtained aerogel possessed a light density of 0.0264 g/cm³ and a porosity of more than 98.2%. It was able to withstand a weight as much as 2500 times with the maximum force (1479.5 N) to break up 0.2 g of an aerogel by compression strength testing and was stable in the aquatic environment, enabling it to be reused five times with an adsorption capacity over 90%. The CNF/GO aerogel can recover higher than 85% after 30 consecutive compression recovery cycles, which is convenient for the reusability of this material in wastewater treatments. The obtained aerogel also showed a good interaction between the component phases, a high thermal stability, a 3D network structure combined with thin walls and pores with a large specific surface area. In addition, the aerogel also exhibited a fast adsorption rate for methylene blue (MB) adsorption, a type of waste from the textile industry that pollutes water sources, and it can adsorb more than 99% MB in water in less than 20 min. The excellent adsorption of MB onto the CNF/GO aerogel was driven by electrostatic interactions, which agreed with the pseudo-second-order kinetic model with a correlation coefficient R² = 0.9978. The initial results show that the CNF/GO aerogel is a highly durable “green” light material that might be applied in the treatment of domestic organic waste water and is completely recoverable and reusable.