The removal of dyes from water is an area of great relevance worldwide, and new technologies and materials are therefore continuously investigated. In this context, bioadsorbents based on cellulose nanofibrils (CNF) and poly(vinylbenzyl)trimethylammonium chloride (PClVBTA) were developed to study the adsorption of methyl orange (MO) dye. Radical polymerization enabled the successful creation of these adsorbents, with CNF modifying the physicochemical properties of the base material, as evidenced by Fourier transform infrared spectroscopy (FT-IR), thermogravimetric analysis (TGA), scanning electron microscopy (SEM), and dynamic compression tests. The adsorption capacities improved with increasing CNF content, reaching an experimental adsorption capacity of 579 mg g−1 for MO when 1.00 wt% CNF was used. The experimental data were fitted to the Elovich kinetic and Langmuir isothermal models, and the thermodynamic parameters indicated that the adsorption is favorable. The adsorption of MO was confirmed by FT-IR, BET isotherms, and energy dispersive spectroscopy (EDS) analysis. Interfering salts in the aqueous medium did not affect significantly, and the adsorbent material was reusable for up to five cycles. Theoretical studies highlighted π interactions and hydrogen bonding, demonstrating that the incorporation of CNF improves the sustainability and performance of the adsorbents in water purification.