We combine tensile strength analysis and X-ray scattering experiments to establish a detailed understanding of the microstructural coupling between liquid-crystalline elastomer (LCE) networks and embedded magnetic core-shell ellipsoidal nanoparticles (NPs). We study the structural and magnetic re-organization at different deformations and NP loadings, and the associated shape and magnetic memory features. In the quantitative analysis of a stretching process, the effect of the incorporated NPs on the smectic LCE is found to be prominent during the reorientation of the smectic domains and the softening of the nanocomposite. Under deformation, the soft response of the nanocomposite material allows the organization of the nanoparticles to yield a permanent macroscopically anisotropic magnetic material. Independent of the particle loading, the shape-memory properties and the smectic phase of the LCEs are preserved. Detailed studies on the magnetic properties demonstrate that the collective ensemble of individual particles is responsible for the macroscopic magnetic features of the nanocomposite.