Memory encoding by cyclic shear is a reliable process to store information in jammed solids, yet its underlying mechanism and its connection to the amorphous structure are not fully understood. When a jammed sphere packing is repeatedly sheared with cycles of the same strain amplitude, it optimizes its mechanical response to the cyclic driving and stores a memory of it. We study memory by cyclic shear training as a function of the underlying stability of the amorphous structure in marginally stable and highly stable packings, the latter produced by minimizing the potential energy using both positional and radial degrees of freedom. We find that jammed solids need to be marginally stable in order to store a memory by cyclic shear. In particular, highly stable packings store memories only after overcoming brittle yielding and the cyclic shear training takes place in the shear band, a region which we show to be marginally stable.