There is a growing interest in using naturally derived materials to generate adsorbent materials that can improve water quality by removing industrially derived pollutants such as dyes. In this work, composite beads were prepared from wood-based cellulose nanofibrils (CNF) and Tara gum (TG) by their co-dissolution in urea/sodium hydroxide alkaline media followed by co-regeneration in acidic media. The obtained beads were characterized by Fourier transformed infrared with attenuated total reflectance (FTIR-ATR), X-ray diffraction (XRD), thermogravimetric analysis (TGA), elemental analysis (EA), and scanning electron microscopy (SEM), while the dye adsorption capacity was followed by UV–Vis spectroscopy. The results showed that a 40% substitution of the CNF with TG resulted in lightweight beads with 54% less solid content that maintained similar dimensions. These beads were tested for methylene blue (MB) adsorption at varying sorbent and pollutant concentrations. Methylene blue was selected as it is a common dye used as a redox indicator for tissue staining, dairy testing, microbiology, and in the textile and leather industries. Overall, the TG-CNF composite beads showed improved performance on dye adsorption, with 39.6% more capture when compared to the neat cellulose beads. The maximum adsorption capacity was calculated as 13.7 mg/g, utilizing an adsorption isotherm (2–15 ppm) fitted into the Langmuir model.