The best way to track an "off" phone is to (secretly) install a chip, connected to the phone's battery supply. Thus, even when the phone is "off", that added chip would still be "on". In this case, it's not really the phone itself that's being tracked, but that chip. As long as you had a battery, the same tracking technique would work for portable laptops, your shoe, or even a gun. (This is how the ATF's "fast and furious" program tracking guns was supposed to work -- but the batteries drained too fast).
Another way of looking at the problem is defining, exactly, what "off" means. Conceptually, your mobile phone is "off" when you aren't using it. A secondary, ulta low power "baseband" processor remains "on" to listen to the cell tower. When the baseband processor detects an incoming call, it turns the rest of the phone back "on". Especially with older "feature phones", turning the phone "completely off" would sometimes leave the baseband processor still "on", thus allowing you to be tracked. For example, sometimes the phone had a timing circuit that will occasionally turn on the baseband to grab SMS messages every 10 minutes -- even though it was "off" enough that it couldn't receive incoming calls.
Even if the baseband is off, many phones still have an alarm clock that remains "on". As the Nokia 1100 manual states "If the alarm time is reached while the phone is switched off, the phone switches itself on". This timer circuit emits extremely low EMF that may be detectable. Given an area in the countryside where insurgents are hiding, it might be enough to locate them.
The moral of this is that just because you define the phone as "off" doesn't mean that it's 100% completely "off" all the time.
What does "track" mean? Sometimes it simply means "detect". Radio circuits are reactive -- even with the batteries removed. You can blast out a radio wave of a certain frequency and get radio patterns in response [example]. This detection can identify a specific model of cell phone, but it can't get personal information (such as phone number, IMSI, IMEI, ICCID) that would require some part of the device to be "on".
What I'm trying to show here is while the statement "track phone while off" can be true depending on what they mean, it's false in practice. If you turn your iPhone/Android off, the NSA cannot track you by your phone number (or the other personal IDs).
@collinrm @ErrataRob Read up on MASINT. Signature of EM radiation emitted (or resp.) by a specific, individual device can be fingerprinted.
— pbr90x (@pbr90x) July 23, 2013
.@ErrataRob Of course if the NSA elects to modify your phone's firmware, removing the battery is the only way to ensure it's actually "off".
— Marsh Ray (@marshray) July 23, 2013
The NSA is tracking @erratarob's shoes! http://t.co/4be2lvrM8c …
— Dave Piscitello (@securityskeptic) July 23, 2013