Using rock magnetism and thermal modeling, we evaluate the candidate minerals responsible for strong magnetic anomalies in the Terra Sirenum and Terra Cimmeria regions of Mars' southern highlands. We assume an early global dynamo field similar in strength to the present Earth's field, enduring about 500 Myr after accretion and core formation, and a basaltic crust containing no more than 4--7 weight% of magnetic minerals. Thermal evolution models with a wide variety of initial crustal thicknesses, distributions of radioactive elements, and thermal expansion coefficients all yield similar thermal histories for the crust: warming in the first ~1000 Myr (due mainly to radioactive heating) followed by monotonic cooling for the remainder of Mars' history. Primary thermoremanent magnetization (TRM) acquired by intrusive and extrusive bodies during the first 500 Myr was in part thermally demagnetized by general crustal warming after the dynamo field disappeared, from 500 to 1000 Myr. The Curie point isotherms around 1000 Myr established the maximum depth of TRM-bearing crust. Shock and heating due to impacts demagnetized the uppermost ~10 km of the crust around the same time, resulting in potential magnetic layer thicknesses of 15--20 km for pyrrhotite, 40--50 km for magnetite, and 50--60 km for hematite. Other magnetic phases, such as iron and finely exsolved low-Ti titanohematite, are possible but less likely in a basaltic crust under oxidizing conditions. The prime candidates, in order of likelihood, are single-domain magnetite (0.2--0.4 volume% or 0.4--0.8 weight% required), single-domain pyrrhotite (1--2 volume% or 2--4 weight%), and either multidomain (>15 ¿m) or 5--15 ¿m single-domain hematite or a mixture of both (1.5--3 volume% or 3--6 weight%). A composite source with different combinations of these minerals at different depths is entirely possible. Viscous decay of TRM is difficult to assess without detailed knowledge of the distribution of minerals and blocking temperatures with depth but would increase the amounts of magnetic material required.