Important constraints on the properties of the Anomalous X-ray Pulsars (AXPs) and Soft Gamma-Ray Repeaters (SGRs) can be provided by their associations with supernova remnants (SNRs). We have made a radio search for SNRs towards the AXPs RX J170849-400910 and 4U 0142+61 - we find that the former lies near a possible new SNR with which it is unlikely to be physically associated, but see no SNR in the vicinity of the latter. We review all claimed pairings between AXPs and SNRs; the three convincing associations imply that AXPs are young (< 10 000 yr) neutron stars with low projected space velocities (< 500 km/s). Contrary to previous claims, we find no evidence that the density of the ambient medium around AXPs is higher than that in the vicinity of radio pulsars. Furthermore, the non-detection of radio emission from AXPs does not imply that these sources are radio-silent. We also review claimed associations between SGRs and SNRs. We find none of these associations to be convincing, consistent with a scenario in which SGRs and AXPs are both populations of high-field neutron stars ("magnetars") but in which the SGRs are an older or longer-lived group of objects than are the AXPs. If the SGR/SNR associations are shown to be valid, then SGRs must be high-velocity objects and most likely represent a different class of source to the AXPs. Comment: 13 pages, 3 embedded EPS figures. Minor alterations following referee's report; no significant changes. Accepted to ApJ