The present work offers a comprehensive description of the acid-induced gelation of carboxymethylcellulose (CMC), a water-soluble derivative of cellulose broadly used in numerous applications ranging from food packaging to biomedical engineering. Linear viscoelastic properties measured at various pH and CMC contents allow us to build a sol-gel phase diagram and show that CMC gels exhibit broad power-law viscoelastic spectra that can be rescaled onto a master curve following a time-composition superposition principle. These results demonstrate the microstructural self-similarity of CMC gels and inspire a mean-field model based on hydrophobic interchain association that accounts for the sol-gel boundary over the entire range of CMC content under study. Neutron scattering experiments further confirm this picture and suggest that CMC gels comprise a fibrous network cross-linked by aggregates. Finally, low-field NMR measurements offer an original signature of acid-induced gelation from a solvent perspective. Altogether, these results open avenues for the precise manipulation and control of CMC-based hydrogels.