Bacterial cellulose (BC) consists of a complex three-dimensional organization of ultrafine fibers which provide unique material properties such as softness, biocompatibility, and water-retention ability, of key importance for biomedical applications. However, there is a poor understanding of the molecular features modulating the macroscopic properties of BC gels. We have examined chemically pure BC hydrogels and composites with arabinoxylan (BC-AX), xyloglucan (BC-XG), and high molecular weight mixed-linkage glucan (BC-MLG). Atomic force microscopy showed that MLG greatly reduced the mechanical stiffness of BC gels, while XG and AX did not exert a significant effect. A combination of advanced solid-state NMR methods allowed us to characterize the structure of BC ribbons at ultra-high resolution and to monitor local mobility and water interactions. This has enabled us to unravel the effect of AX, XG, and MLG on the short-range order, mobility, and hydration of BC fibers. Results show that BC-XG hydrogels present BC fibrils of increased surface area, which allows BC-XG gels to hold higher amounts of bound water. We report for the first time that the presence of high molecular weight MLG reduces the density of clusters of BC fibrils and dramatically increases water interactions with BC. Our data supports two key molecular features determining the reduced stiffness of BC-MLG hydrogels, that is, (i) the adsorption of MLG on the surface of BC fibrils precluding the formation of a dense network and (ii) the preorganization of bound water by MLG. Hence, we have produced and fully characterized BC-MLG hydrogels with novel properties which could be potentially employed as renewable materials for applications requiring high water retention capacity (e.g. personal hygiene products).