A cellulose/xyloglucan framework is considered to form the basis for the mechanical properties of primary plant cell walls and hence to have a major influence on the biomechanical properties of growing, fleshy plant tissues. In this study, structural variants of xyloglucan have been investigated as components of composites with bacterial cellulose as a simplified model for the cellulose/xyloglucan framework of primary plant cell walls. Evidence for molecular binding to cellulose with perturbation of cellulose crystallinity was found for all xyloglucan types. High molecular mass samples gave homogeneous centimeter-scale composites with extensive cross-linking of cellulose with xyloglucan. Lower molecular mass xyloglucans gave heterogeneous composites having a range of microscopic structures with little, if any, cross-linking. Xyloglucans with reduced levels of galactose substitution had evidence of self-association, competitive with cellulose binding. At comparable molecular mass, fucose substitution resulted in a modest promotion of microscopic features characteristic of primary cell walls. Taken together, the data are evidence that galactose substitution of the xyloglucan core structure is a major determinant of cellulose composite formation and properties, with additional fucose substitution acting as a secondary modulator. These conclusions are consistent with reported structural and mechanical properties of Arabidopsis mutants lacking specific fucose and/or galactose residues.