Climate variations on decadal time scales, such as droughts and changes in extreme weather events, have a great impact on society and therefore reliable predictions of these variations would be valuable. Unfortunately, the mechanisms of this variability have remained unclear partly due to observational limitations and partly due to limitations of current climate models. The purpose of this dissertation research is to improve understanding of decadal variability and predictability through analysis of simulations and simple stochastic models. As a first step, the most predictable components of 2m-air temperature are identified through an objective procedure called Average Predictability Time (APT) analysis. This analysis reveals that the most predictable components of internal variability in coupled atmosphere-ocean models are remarkably similar to the most predictable components of climate models without interactive ocean dynamics (ie, models whose ocean is represented by a 50m-deep slab ocean mixed layer with no interactive currents). This result suggests that interactive ocean circulation is not essential for the existence of multi-year predictability previously identified in coupled models and observations. A new stochastic model is proposed that captures the essential physics of decadal variability in the latter models. This model is based on the linearized primitive equations for the atmosphere, a slab mixed-layer model for the ocean, a gray radiation scheme for radiative effects, and a diffusive scheme for vertical turbulent eddy fluxes. It is shown that this model generates new low-frequency peaks in the power spectrum that do not exist in either the atmospheric model alone or in the slab ocean mixed layer model alone.