Secular Kozai oscillations, induced by a distant stellar companion and acting in concert with tidal dissipation, is one of the major channels for the production of hot Jupiters and close stellar binaries. This mechanism is particularly attractive due to the high degree of misalignment between the stellar spin and planet orbital angular momentum axes that has been observed in many systems. In the typical Kozai picture, this misalignment is thought to be the result of large variation in the planet's orbital axis, while the stellar spin orientation remains mostly fixed. Here we demonstrate that gravitational interactions between the stellar spin and the planetary orbit can induce a variety of dynamical behavior for the stellar spin evolution during the Kozai cycle. In particular, in systems hosting giant planets, the stellar spin exhibits rich, often strongly chaotic dynamics, with Lyapunov times as short as 10 Myr. This arises from secular spin-orbit resonances and resonance overlaps. Therefore, in systems with distant stellar companions, planets can strongly influence the spin evolution of their host stars. A thorough understanding of the spin-orbit dynamics is thus essential for understanding the observed distribution of obliquity angles in hot Jupiter systems. We show that in the presence of tidal dissipation, the memory of chaotic spin evolution can be preserved, leaving an imprint on the final spin-orbit misalignment angles.