Nanofibrillar hydrogels are an important class of biomaterials with applications as catalytic scaffolds, artificial extracellular matrixes, coatings, and drug delivery materials. In the present work, we report the results of a comprehensive study of nanofibrillar hydrogels formed by cellulose nanocrystals (CNCs) in the presence of cations with various charge numbers and ionic radii. We examined sol gel transitions in aqueous CNC suspensions and the rheological and structural properties of the CNC hydrogels. At a particular CNC concentration, with increasing charge and cation size, the dynamic shear moduli and mesh size in the hydrogel increased. These effects were ascribed to a stronger propensity of CNCs for side-by-side association. The resulting hydrogels had an isotropic nanofibrillar structure. A combination of complementary techniques offered insight into structure-property relationships of CNC hydrogels, which are important for their potential applications.