Gelation of aqueous methylcellulose (MC) solutions upon heating has been shown to result from the formation of a network of semiflexible fibrils, with diameters of 15 +/- 2 nm. Here, we investigate the impact of MC molecular weight on the elasticity and structure of aqueous gels at concentrations between 0.1 and 3 wt %. Small-amplitude oscillatory shear measurements conducted at a fixed concentration reveal that the gel modulus increases monotonically by a factor of 5 for weight-average molecular weights (M-w) between 22 and 550 kg/mol. Small-angle X-ray scattering data, fit to a semiflexible cylinder model, demonstrate that the fibril radius, Kuhn length, and volume fraction are approximately constant throughout this molecular weight range. Small-angle light scattering shows that the fibrillar-rich and fibrillar-depleted domains within the gel are associated with an essentially invariant heterogeneity correlation length. Direct visualization by cryo-TEM reveals that lower molecular weight MC forms fibrils of lower average length. The distribution of fibril lengths measured by cryo-TEM and the distribution of the polymer chain contour lengths are similar, especially for shorter chains, and these features are correlated to network connectivity. We propose that the underlying fibril structure consists of bundles of polymer chains with a preferred orientation coincident with the fibril axis, while the fibril diameter is controlled by a circumferential helical pitch associated with the single chain Kuhn length and interactions between chains.