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.