Software-Defined Metamaterials (SDMs) show a strong potential for advancing the engineered control of electromagnetic waves. As such, they are envisioned to enable a variety of exciting applications, among others in the domains of smart textiles, high-resolution structural monitoring, and sensing in challenging environments. Many of the applications envisage deformations of the SDM structures, such as their bending, stretching or rolling, which implies that the locations of metamaterial elements will be changing relative to one another. In this paper, we argue that if the metamaterial elements would be accurately localizable, this location information could potentially be utilized for enabling novel SDM applications, as well as for optimizing the control of the elements themselves. To enable their localization, we assume that these elements are controlled wirelessly through a Terahertz (THz)-operating nanonetwork. We consider the elements to be power-constrained, with their sole powering option being to harvest energy from different environmental sources. By means of simulation, we demonstrate sub-millimeter accuracy of the two-way Time of Flight (ToF)-based localization, as well as high availability of the service (i.e., consistently more than 80% of the time), which is a result of the low energy consumed in the localization process. Finally, we qualitatively characterize the latency of the proposed localization service, as well as outline several challenges and future research directions.