Environmental stress during early development in animals can have profound effects on adult phenotypes via programmed changes in gene expression. Using the nematode C. elegans, we demonstrated previously that adults retain a cellular memory of their developmental experience that is manifested by differences in gene expression and life history traits; however, the sophistication of this system in response to different environmental stresses, and how it dictates phenotypic plasticity in adults that contribute to increased fitness in response to distinct environmental challenges, was unknown. Using transcriptional profiling, we show here that C. elegans adults indeed retain distinct cellular memories of different environmental conditions. We identified approximately 500 genes in adults that entered dauer due to starvation that exhibit significant opposite ("seesaw") transcriptional phenotypes compared to adults that entered dauer due to crowding, and are distinct from animals that bypassed dauer. Moreover, we show that two-thirds of the genes in the genome experience a 2-fold or greater seesaw trend in gene expression, and based upon the direction of change, are enriched in large, tightly linked regions on different chromosomes. Importantly, these transcriptional programs correspond to significant changes in brood size depending on the experienced stress. In addition, we demonstrate that while the observed seesaw gene expression changes occur in both somatic and germline tissue, only starvation-induced changes require a functional GLP-4 protein necessary for germline development, and both programs require the Argonaute CSR-1. Thus, our results suggest that signaling between the soma and the germ line can generate phenotypic plasticity as a result of early environmental experience, and likely contribute to increased fitness in adverse conditions and the evolution of the C. elegans genome.