We describe a simple method of preparation of a carboxymethylcellulose magnetic composite (CMC-MC), which was properly characterized and used for the removal of toluidine blue (TB), a cationic dye, from aqueous media. CMC is a biodegradable water-soluble polymer, with negative charges in its structure that favor the interaction with cationic molecules. The composite resulting from its combination with magnetic nanoparticles form is especially efficient for the treatment of contaminated water. The initial experiments of toluidine blue dye removal in batch mode at room temperature (298 K) showed that when using the CMC-MC a higher efficiency (36%) and capacity (83.7 mg/g) of adsorption were observed than the corresponding results for the pristine magnetic particle (4.0% and 9.0 mg/g, respectively). We also examined the changes in the adsorptive capacity of the CMC-MC when we varied the pH of the medium, the interaction time, and the initial concentration of the toluidine TB dye. The process of removal of the contaminant by the CMC-MC followed a Langmuir-type isotherm, indicating the formation of a monolayer of the adsorbed dye on the surface of the composite. We were able to establish that the pseudo-second-order model is the predominant kinetic mechanism during the adsorption process, which was shown to be exothermic. In reuse tests, we have shown that the material can be used six consecutive times without significant loss of its adsorptive characteristics. Our results indicate that the magnetic composite of carboxymethylcellulose is a promising material for the economical and sustainable removal of the TB dye from aqueous media.