The interaction strength of sodium ions (Na+) with cellulose is investigated from first principles for varying degrees of water content. We find that the interaction of water molecules and Na+ can be studied independently at the various OH groups in cellulose which we categorize as two different types. In the absence of water, Na+ forms strong ionic bonds with the OH groups of cellulose. When water molecules are anchored to the OH groups via hydrogen bonds, Na+ can eventually no longer bind to the OH groups, but will instead interact with the oxygen atoms of the water molecules. Due to the rather weak attachment of the latter to the OH groups, Na+ becomes effectively more mobile in the fully hydrated cellulose framework. The present study thus represents a significant step toward a first-principles understanding of the experimentally observed dependence of ionic conductivity on the level of hydration in cellulose network.