The spin angular momentum S of a supermassive black hole (SBH) precesses due to torques from orbiting stars, and the stellar orbits precess due to dragging of inertial frames by the spinning hole. We solve the coupled post-Newtonian equations describing the joint evolution of S and the stellar angular momenta Lj, j = 1...N in spherical, rotating nuclear star clusters. In the absence of gravitational interactions between the stars, two evolutionary modes are found: (1) nearly uniform precession of S about the total angular momentum vector of the system; (2) damped precession, leading, in less than one precessional period, to alignment of S with the angular momentum of the rotating cluster. Beyond a certain distance from the SBH, the time scale for angular momentum changes due to gravitational encounters between the stars is shorter than spin-orbit precession times. We present a model, based on the Ornstein-Uhlenbeck equation, for the stochastic evolution of star clusters due to gravitational encounters and use it to evaluate the evolution of S in nuclei where changes in the Lj are due to frame dragging close to the SBH and to encounters farther out. Long-term evolution in this case is well described as uniform precession of the SBH about the cluster's rotational axis, with an increasingly important stochastic contribution when SBH masses are small. Spin precessional periods are predicted to be strongly dependent on nuclear properties, but typical values are 10-100 Myr for low-mass SBHs in dense nuclei, 100 Myr - 10 Gyr for intermediate mass SBHs, and > 10 Gyr for the most massive SBHs. We compare the evolution of SBH spins in stellar nuclei to the case of torquing by an inclined, gaseous accretion disk.