Polysaccharides are finding an increasing number of applications in medical and pharmaceutical fields thanks to their biodegradability, biocompatibility, and in some cases bioactivity. Two approaches were applied to use hemicelluloses as crosslinkers to tune the structural and mechanical properties of nanofibrillated cellulose (NFC) hydrogel scaffolds, and thus to investigate the effect of these properties on the cellular behavior during wound healing application. Different types of hemicellulose (galactoglucomannan (GGM), xyloglucan (XG), and xylan) were introduced into the NFC network via pre-sorption (Method I) and in situ adsorption (Method II) to reinforce the NFC hydrogels. The charge density of the NFC, the incorporated hemicellulose type and amount, and the swelling time of the hydrogels were found to affect the pore structure, the mechanical strength, and thus the cells’ growth on the composite hydrogel scaffolds. The XG showed the highest adsorption capacity on the NFC, the highest reinforcement effect, and facilitated/promoted cell growth. The pre-sorbed XG in the low-charged NFC network with a lower weight ratio (NFC/XG-90:10) showed the highest efficacy in supporting the growth and proliferation of fibroblast cells (NIH 3T3). These all-polysaccharide composite hydrogels may work as promising scaffolds in wound healing applications to provide supporting networks and to promote cells adhesion, growth, and proliferation.