The mechanical behavior of disordered materials, such as dense suspensions, glasses, and granular materials, depends on their thermal and mechanical history. Under periodic driving, these materials can evolve into states that encode a memory of their annealing. Such memory effects have been observed experimentally in systems ranging from sheared non-Brownian suspensions to crumpled elastic sheets and in atomistic simulations. Here, we show that a quenched mesoscopic elastoplastic model of a sheared amorphous solid reproduces the phenomena of self-organization and memory formation under mechanical annealing. We analyze sample-to-sample fluctuations under readout protocols and demonstrate their connection to the irreversibility transition. Our model allows us to understand in detail the mechanical processes underlying memory formation. We find that annealing by cyclic shear leads to the self-organization of plasticity, which can be characterized by a density of local mechanical stress thresholds. These thresholds exhibit anisotropy, depending on their alignment with the driving direction. The interplay between these thresholds dictates how the driving history-particularly its direction and amplitude-is imprinted into the material's local structure. We develop readout protocols capable of accessing both the amplitude and the direction of the mechanical training. Our findings can be understood within the framework of return point memory which emerges as a result of mechanical annealing. Building on this, we develop a Preisach-like model of directional memory that describes well our numerical results. We conclude with a discussion of similarities of the evolution of plasticity under mechanical annealing and adaptive evolution in changing environments.