Cessation of flow in simple yield stress fluids results in a complex stress relaxation process that depends on the preceding flow conditions and leads to finite residual stresses. To assess the microscopic origin of this phenomenon, we combine experiments with largescale computer simulations, exploring the behavior of jammed suspensions of soft repulsive particles. A spatio-temporal analysis of microscopic particle motion and local particle configurations reveals two contributions to stress relaxation. One is due to flow induced accumulation of elastic stresses in domains of a given size, which effectively sets the unbalanced stress configurations that trigger correlated dynamics upon flow cessation. This scenario is supported by the observation that the range of spatial correlations of quasi-ballistic displacements obtained upon flow cessation almost exactly mirrors those obtained during flow. The second contribution results from the particle packing that reorganize to minimize the resistance to flow by decreasing the number of locally stiffer configurations. Regaining rigidity upon flow cessation then effectively sets the magnitude of the residual stress. Our findings highlight that flow in yield stress fluids can be seen as a training process during which the material stores information of the flowing state through the development of domains of correlated particle displacements and the reorganization of particle packings optimized to sustain the flow. This encoded memory can then be retrieved in flow cessation experiments.