Gravitational wave (GW) astronomy using a pulsar timing array requires high-quality millisecond pulsars (MSPs), correctable interstellar propagation delays, and high-precision measurements of pulse times of arrival. Here we identify noise in timing residuals that exceeds that predicted for arrival time estimation for MSPs observed by the North American Nanohertz Observatory for Gravitational Waves. We characterize the excess noise using variance and structure function analyses. We find that 26 out of 37 pulsars show inconsistencies with a white-noise-only model based on the short timescale analysis of each pulsar, and we demonstrate that the excess noise has a red power spectrum for 15 pulsars. We also decompose the excess noise into chromatic (radio-frequency-dependent) and achromatic components. Associating the achromatic red-noise component with spin noise and including additional power-spectrum-based estimates from the literature, we estimate a scaling law in terms of spin parameters (frequency and frequency derivative) and data-span length and compare it to the scaling law of Shannon & Cordes. We briefly discuss our results in terms of detection of GWs at nanohertz frequencies.