As creepy as it might seem to many people (including myself), I absolutely understand why a government might want to collect such information and perform analysis on it. A government might even wish to do so in a period of absolute peace, let alone when explicitly threatened by known terrorists. (Like La Professora, I shall pass on the rhetorical quagmire that is the definition of " 'War' on 'Terror' ". Nope, not going there in this post.) Such efforts occasionally approach the disturbingly surreal, as is the (thankfully overruled) idea of finding terrorist in San Francisco by looking at sales of falafel.
I agree that if one does not even attempt to change the status quo by using the ballot box, then one's complaints about said status begin to sound more like bellyaching than Civil debate (as opposed to "civil" debate, which is rare on the InterTubes indeed.) However, our views diverge on the "No-Fly List", which is not something that a person can actually do much about, to the point of not even knowing if one is on the list until one is trying to check in at the airport. At last count, the list contained 300,000+ names. To put that in perspective, this means that some 0.1% of people in America—about one in a thousand—are on this list. When was the last time you were in a mall on a Saturday? There's one. What about on a university (or even a large high school) campus? At least one. Are you near a mosque or a falafel stand? The FBI would have you believe that those are terrorist hotbeds, in Des Moines or Damascus, so there would be lots more.
Assuming no duplicates (because we all know how consistently names in non-Roman languages get transliterated to English), deceased (I wonder how many of the 9/11 hijackers are still on this list) or members of the US Senate, that's over three hundred thousand people who are too dangerous to be allowed on airplanes (er, see below), in spite of otherwise being restricted to carrying liquids in three oz. containers/quart baggies, no blades of any kind and the ubiquitous humiliation that is the removal footwear and belts. (Lighters and safety matches, on the other hand, apparently pose no security threat on planes whatsoever and can be carried aboard, even in opaque baggies.) These people are too dangerous to be allowed to fly, but they are allowed to take trains, buses and ferries. They are allowed to buy fertilizer and rent moving vans. I don't know if they're allowed to take flying lessons, but there are general aviation flights which would not turn them away, nor necessarily ask for ID, let alone call up the TSA to check the "No-Fly List".
My favorite security expert, Bruce Schneier, has said many times, in essays and presentations, that he doesn't care if Osama bin Laden is on his flight, as long as the guy isn't bringing a bomb aboard or otherwise able to overpower the crew and control the plane.
Ok, let's step back from the administrative nuttiness that this list represents and look at the constitutionality of such a list. It is clear that the Constitution does not explicitly assert a Right to Travel. However the First Amendment grants the Right to Free Assembly, and I would argue that the freedom to assemble, especially as the Framers would've understood it, necessitates the freedom to travel to the point of assembly. And it's worth noting that even though technology affords us with ways to virtually assemble, there is a vast difference between a million avatars marching (flying, slithering, etc.) on Second Life Washington and a million physical beings heading to the Mall. (I realize that this difference is sure to diminish as the technology seeps into governments' and politicians' day-to-day activities, but it will be a long time coming.)
Additionally, though constitutionally less sound, I would argue that a "No-Fly List" violates habeas corpus, though certainly not in the same way as actually holding a person in custody without a writ. What if a person had to travel to or from the continental US to Alaska or Hawaii to see a dying relative? In Miami? Are they suppose to take the Pan-American Highway? How many passenger liners connect Honolulu to San Francisco? Via the Panama Canal? As far as I know, there are no "dying grandma" exemptions to the "No-Fly List". We treat convicted criminals with more respect.
Imagine if the list was, instead, a "No-Car List": that is to say, a list of people who are not allowed to ride in cars (or motorcycles). Many New Yorkers may not even notice this as being a restriction (depending on how one defines taxis). People in the Northeast, especially ones living in larger cities, might find this inconvenient, but there are enough public transit solutions to cope most of the time. Things start to get harder as one heads West, until one gets to Los Angeles, where public transit is as much a comedy as it is a tragedy. In that case, it could easily be argued that to keep an Angeleno from using a car is tantamount to house arrest. (And before you cyclists object, go ride a bike in Metro L.A. for a week, then tell we can talk.)
I do not argue that cars are the same as passenger airplanes. I do suggest that airplanes have made certain, American, lifestyles possible: living two time zones away from your parents, having parents who live two time zones away from each other, having siblings who live literally in the four corners of the country. And now, those lifestyles are only possible because of easy air travel. To take that away from 0.1% of the population for reasons that cannot be disclosed to the public at large nor the persons affected is contrary to the spirit of what America stands for.
The Declaration of Independence implied a person's right to travel by asserting that everyone has a right to Liberty and the Pursuit of Happiness. The Preamble to the Constitution further asserts that it is for "secur[ing] the Blessing of Liberty", one of which is surely the right to move about as one pleases, both as to where and how. And as a nation of Immigrants (I include myself in that number) and Migrants, how can we ask the world to "[give us] your tired, your poor,/Your huddled masses yearning to breath free" and then tell them that they have to take a train?
 My wife is Austrian, and we live in the house her father grew up in, sharing the property with her paternal grandmother. My in-laws are two streets away, about five minutes by foot, in the house my wife grew up in. My brother-in-law lives in the house behind her parents, purchased from the estate of the deceased neighbor. Her six cousins and their families live within a half hour drive of our house, most of them living in our town. This is, as far as I can tell, still the norm in Austria, as well as most of continental Europe (the UK and Ireland being notable exceptions), though this pattern is shifting towards the "American" model, as trans-EU employment opportunities increase and families become more "nuclear".