Using deep, high-resolution optical imaging from the Next Generation Virgo Cluster Survey, we study the properties of nuclear star clusters (NSCs) in a sample of nearly 400 quiescent galaxies in the core of Virgo with stellar masses 10^5^<~M*/M_{sun}_<~10^12^. The nucleation fraction reaches a peak value f_n_~90% for M*~10^9^M_{sun}_ galaxies and declines for both higher and lower masses, but nuclei populate galaxies as small as M*~5x10^5^M_{sun}_. Comparison with literature data for nearby groups and clusters shows that at the low-mass end nucleation is more frequent in denser environments. The NSC mass function peaks at M_NSC_~7x10^5^M_{sun}_, a factor 3-4 times larger than the turnover mass for globular clusters (GCs). We find a nonlinear relation between the stellar masses of NSCs and those of their host galaxies, with a mean nucleus-to-galaxy mass ratio that drops to M_NSC_/M*~3.6x10^-3^ for M*~5x10^9^M_{sun}_ galaxies. Nuclei in both more and less massive galaxies are much more prominent: M_NSC_{propto}M_*_^0.46^ at the low-mass end, where nuclei are nearly 50% as massive as their hosts. We measure an intrinsic scatter in NSC masses at a fixed galaxy stellar mass of 0.4dex, which we interpret as evidence that the process of NSC growth is significantly stochastic. At low galaxy masses we find a close connection between NSCs and GC systems, including very similar occupation distributions and comparable total masses. We discuss these results in the context of current dissipative and dissipationless models of NSC formation.