I did a little bit of reading about the legal basis for searching airplane passengers, and for searching passengers of other kinds of mass transit (trains, subways, buses).
Here's a link to what I read (from Ferdico, Fratella, and Totten, Criminal Procedure for the Criminal Justice Professional, 2009): on airport searches; on public transit searches.
Here's what I understand as a total non-lawyer:
These kinds of searches are considered "administrative searches." Administrative searches are performed to see whether you're in compliance with some statute or regulation, not to gather evidence for criminal charges. So they have much less stringent Fourth Amendment restrictions. For example, the fire marshal doesn't need a search warrant in order to inspect a business to see whether they comply with fire code.
If the government has some important "special need" that outweighs the privacy invasion, they can perform warrantless searches. This has been upheld by the Supreme Court.
Of course, even in searches performed as part of a criminal investigation, you don't need a warrant if the subject consents to a search.
At airports, the government can be considered to have a "special need" to ensure safety. But more often, the passenger is legally considered to have given implied consent for a search of their bags and their person by choosing to fly.
On public transit, the courts have said warrantless searches are legal because of the government's compelling interest in ensuring public safety. They've reasoned that the privacy intrusion is minimal compared to the potential efficacy of random searches at stopping a terrorist attack. (This was specifically about bag searches, not searches of anyone's person.)
Again, I'm not a lawyer, so take my opinion with a few grains of salt. But to me, this sounds like a pretty slippery slope. Terrorism is fundamentally a criminal activity. You could argue that lots of other criminal activities harm the public safety, too. Why not just start searching everyone on the street? After all, muggings are bad for the public safety. So is the drug trade. Doesn't the importance of preventing those crimes outweigh the minor loss of privacy in getting patted down? And then you can just scratch out the Fourth Amendment.
And if the TSA takes upon itself the right to start scanning and patting down all train passengers, bus passengers, and subway passengers, why not argue that those passengers consented to the search when they chose to use that form of transportation? Why not argue that drivers consented to having their cars searched when they chose to drive on a public highway? After all, terrorists drive cars. Some of them even use cars as bombs. Doesn't the government have a compelling interest in preventing car bombings?
It really sounds to me like "terrorism" is some magic word of power. Everyone is so terrified that all you have to do is say "We're doing it to prevent terrorism!" and the Constitution no longer applies.