People occasionally ask me what the U.S. government may do with respect to the speech of noncitizens. (See also this post by Megan McArdle, guestblogging at InstaPundit, which raises the same issue.) Here's a summary of current First Amendment law on the subject. Note that I report here on what is the law (and what the uncertainties in the law are), rather than opining on what it should be.
1. "Noncitizens," not "immigrants." First, a simple but often-forgotten note: The question here is not about the speech of immigrants; it's about the speech of noncitizens. The millions of immigrants who are citizens (for instance, me) are treated exactly the same way for First Amendment purposes as any other citizens. More broadly, we are legally like native-born U.S. citizens in virtually all respects.
There are a few exceptions: We can't be President or Vice-President; if we lied on our naturalization applications, we could be stripped of our citizenship (this is how some former Nazis ended up being stripped of citizenship); and I suspect that in practice we may arouse more scrutiny during security checks, especially if our country of former citizenship is an enemy of the U.S., or harbors many enemies of the U.S. But those are narrow exceptions, and the rule is that immigrant citizens have the same rights, including the same free speech rights, as native-born citizens.
2. Criminal punishment and traditional civil liability: The government may not criminally punish noncitizens — or presumably impose civil liability on them — based on speech that would be protected if said by a citizen. See Bridges v. Wixon (1945).
3. Entry: The government may bar noncitizens from entering the United States because of what they've said or are likely to say, even if the speech would have been constitutionally protected if said by a citizen. See Kleindienst v. Mandel (1972).
4. Deportation for speech alone: The rule is unclear. The leading case, Harisiades v. Shaugnessy (1952), which upheld Harisiades' deportation for being a Communist, speaks about nearly unlimited Congressional power over deportation, but that language is in the section holding that the deportation of Harisiades didn't violate the Due Process Clause. The Court's conclusion that the deportation of Harisiades didn't violate the Free Speech Clause (Harisiades had argued that the deportation violated both clauses) rested on the conclusion that active membership in the Communist Party was substantively unprotected by the First Amendment — both for citizens and noncitizens. (This view that the First Amendment doesn't protect Communist Party membership was the law at the time,)
Lower court cases are likewise mixed. For the view that Harisiades doesn't generally let the government act based on otherwise protected speech by aliens, see American-Arab Anti-Discrim. Comm. v. Reno, 70 F.3d 1045 (9th Cir. 1995), reversed on other grounds, 525 U.S. 471 (1999); Parcham v. INS, 769 F.2d 1001 (4th Cir. 1985). For the view that Harisiades gives Congress nearly unlimited immigration power over aliens, see Price v. INS, 941 F.2d 878 (9th Cir. 1991).
5. Deportation for technical immigration law violation, motivated by the noncitizen's speech: The Court has, however, squarely held that if the government tries to deport someone who has violated immigration law — for instance, by overstaying his visa, or working without authorization — the person may not challenge the deportation on the grounds that he was selectively prosecuted based on his otherwise protected speech. See Reno v. American-Arab Anti-Discrim. Comm. (1999). Outside the immigration context, such selective prosecution claims may generally be made (though they aren't easy to make), and, if they're successful, they can lead courts to throw out the case against the speaker. See Wayte v. United States (1985).
6. Citizenship: It's likewise unclear whether Congress can deny noncitizens citizenship based on speech that would be protected if said by a citizen. For a lower court's argument in favor of such power, see Price: "While a resident alien may not participate in the process of governing the country, naturalized citizens may. Naturalization decisions, therefore, deserve at least as much judicial deference as do decisions about initial admission."
7. Noncitizens may also have statutory rights. I've spoken here just of constitutional rights, which noncitizens have no matter what Congress might do. Noncitizens, and especially permanent residents, also have statutory rights to remain in the country unless they've done (or there's sufficient reason to think they've done) certain bad things — at least until Congress revises the statutes to broaden the grounds for deportation (which it may even do retroactively, since the Ex Post Facto Clause only bars retroactive criminal punishment, and deportation is not treated as criminal punishment).
So if the Executive Branch decides to deport someone, it has to have statutorily authorized grounds, and it has to provide hearings at which an immigration judge decides whether the conditions for deportation are met. (These hearings are required both by federal statute, and, at least as to permanent residents, by the Due Process Clause, on the theory that deprivation of a permanent resident's rights to live here is tantamount to a deprivation of liberty or property.) This last paragraph is just a sketch of the statutory landscape; I am not an expert in immigration law, and can thus speak in detail and with some confidence only about the specifically First Amendment issues.