According to this story on the Guardian and a program I heard on the radio earlier (The Last Word on Today FM), the iPhone 3 and 4 series as well as the iPad with at least iOS 4 stores a file continuously recording the user's longitude, latitude and time stamp. This goes on in the background without the user's consent and regardless of whether they use the GPS capabilities on the phone, as long as the phone is switched on.
Researchers analysing this data were able to use this information to plot every location the phone has been in, including which roads they travelled, where they stopped and how long they were at each location based on the timestamps. This data is synced with iTunes on the computer, making it possible for someone with access to the computer to see all the locations this user has been. The data can also be read directly from the phone by "jail breaking" it, which makes this a concern for those who had their iPhone stolen or lost.
According to the The Last Word programme played on the Irish radio station Today FM, on one phone which was updated to iOS 4, 6 months ago, the phone stored the entire 6 month history of tracking and there is no way of disabling this tracking other than keeping the phone switched off. The location is calculated using cellular triangulation, which means that this tracking can work without a GPS signal. The data will also be carried across to a new iPhone or iPad if the user upgrades and migrates their data.
So far the researchers have not found any sort of location tracking on Android or any other phone operating system, at least their time of publishing.
The full story can be read on The Guardian.