Sean O'Neill at Yahoo!Travel orders his own government-collated travel records via FOIA, and tells you how to do so as well–though he's not necessarily saying it's worth the trouble,
….unless you've been experiencing a problem crossing our nation's borders. For one thing, the records are a bit dull. In my file, for instance, officials had blacked out the (presumably) most fascinating parts, which were about how officials assessed my risk profile. What's more, the records are mainly limited to information that airline and passport control officials have collected, so you probably won't be surprised by anything you read in them. Lastly, there may be a cost. While there was no charge to me when I requested my records, you might charged a fee of up to $50 if there is difficulty in obtaining your records. Of course, there's a cost to taxpayers and to our nation's security resources whenever a request is filed, too.
Depending on how you feel about the use of "our nation's security resources" on keeping records of your travel, that last point might be feature, not bug. Though it's unlikely a flood of FOIA requests will scare the busybodies straight.
O'Neill also explains how and why the government has these records in the first place. It's all worth remembering, as those halcyon days of 15 years ago when you could get on a plane with nothing but a ticket fade from memory:
The commercial airlines send these passenger records to Customs and Border Protection, an agency within the Department of Homeland Security. Computers match the information with the databases of federal departments, such as Treasury, Agriculture, and Homeland Security. Computers uncover links between known and previously unidentified terrorists or terrorist suspects, as well as suspicious or irregular travel patterns. Some of this information comes from foreign governments and law enforcement agencies. The data is also crosschecked with American state and local law enforcement agencies, which are tracking persons who have warrants out for their arrest or who are under restraining orders. The data is used not only to fight terrorism but also to prevent and combat acts of organized crime and other illegal activity.
Officials use the information to help decide if a passenger needs to have additional screening. Case in point: After overseas trips, I've stood in lines at U.S. border checkpoints and had my passport swiped and my electronic file examined. A few times, something in my record has prompted officers to pull me over to a side room, where I have been asked additional questions. Sometimes I've had to clarify a missing middle initial. Other times, I have been referred to a secondary examination….
When did this electronic data collection start? In 1999, U.S. Customs and Border Protection (then known as the U.S. Customs Service) began receiving passenger identification information electronically from certain air carriers on a voluntary basis, though some paper records were shared prior to that. A mandatory, automated program began about 6 years ago. Congress funds this Automated Targeting System's Passenger Screening Program to the tune of about $30 million a year.
A Reason magazine classic from Aug/Sept 2003 on John Gilmore's brave but futile attempt to legally challenge the requirement you show I.D. to get on a plane.