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 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 an increasing charge and size of a cation, the dynamic shear moduli and the mesh size in the hydrogel increased, which was 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, important for their potential applications.