Ryan Singel at Wired offers some useful advice. A sample:
The first rule for most people in getting off a watch list is to accept that you are not on a list.
Most likely, if you are being singled out at the airport for extra scrutiny, or your credit report says you might match a Treasury list, you are the victim of a bad matching algorithm or a vague watch-list entry for some other person.
If you only occasionally get an SSSS on your boarding pass, you likely aren't on a watch list—you've just been elected for random screening, or for buying a one-way ticket. (Real Americans fly roundtrip.)
If your problem is domestic- or international-travel-related, you can try the Department of Homeland Security's new online redress system, called the Traveler Redress Inquiry Program, reintroduced in February. (The old one was so badly designed that Congress opened an investigation). After filling out the form with details, a stymied traveler will need to submit copies of identification documents. You can file online, or submit a version by fax, mail or e-mail.
If DHS determines your name is matching incorrectly to a watch-list entry, it may add you to a white list that gets you through airport security without the extra scrutiny.
If you're attempting to shake free of a list you are actually on, it can only be done by the agency that put you on the list in the first place.
While thinking about air travel and government, you should read James Bovard's February 2004 cover story on the Transportation Security Administration's philosophy of "Dominate. Intimidate. Control ."