Using samples drawn from the Sloan Digital Sky Survey, we study the relationship between local galaxy density and the properties of galaxies on the red sequence. After removing the mean dependence of average overdensity (or "environment") on color and luminosity, we find that there remains a strong residual trend between luminosity-weighted mean stellar age and environment, such that galaxies with older stellar populations favor regions of higher overdensity relative to galaxies of like color and luminosity (and hence of like stellar mass). Even when excluding galaxies with recent star-formation activity (i.e., younger mean stellar ages) from the sample, we still find a highly significant correlation between stellar age and environment at fixed stellar mass. This residual age-density relation provides direct evidence for an assembly bias on the red sequence such that galaxies in higher-density regions formed earlier than galaxies of similar mass in lower-density environments. We discuss these results in the context of the age-metallicity degeneracy and in comparison to previous studies at low and intermediate redshift. Finally, we consider the potential role of assembly bias in explaining recent results regarding the evolution of post-starburst (or post-quenching) galaxies and the environmental dependence of the type Ia supernova rate. Comment: Accepted for publication in MNRAS