Can courts ban any executive order they feel is unconstitutional?
What were the legal grounds for this decision?
You can read the judge's order here. The first thing to note is that the United States District Court for the Western District of Washington did not "nullify" or "ban" Executive Order 13769. Instead the Court issued only a Temporary Restraining Order (TRO), which only temporarily suspends the order while the case is being adjudicated.
As the TRO explains, the standard for issuing a TRO requires the moving party to demonstrate the following:
(1) that he is likely to succeed on the merits,
(2) that he is likely to suffer irreparable harm in the absence of preliminary relief
(3) that the balance of equities tips in his favor
(4) that an injunction is in the public interest
Winter v. Natural Resources Defense Council, inc. 555 U.S. 7, at 20 (2008). In this case, Judge Robart found that all four factors fell in plaintiff's favor, requiring him to issue a temporary restraining order.
Note that TRO's are generally issued very early in the litigation process, before a full hearing is conducted. Judges therefore usually do not go into detail discussing the merits of each party's legal arguments, as they are pressed for time. The state of Washington argued that the President exceeded his statutory authority under the Immigration and Nationality Act, and violated the First and Fifth Amendments of the Constitution when issuing his order. Though Judge Robart found that Washington was likely to suceed on the merits of these arguments, he did not offer a detailed explanation as to why. For that, you are probably going to have to wait until either a preliminary injunction or the final judgment on the merits is issued.
What were the legal grounds for this decision?
No clue yet, but I think we can make an educated guess what happened here. I recently read this article by Andrew McCarthy which offers a highly probable reasoning (trimmed for relevance here, emphasis mine)
The Trump administration’s most consequential folly may be the litigating posture it has put itself in. It was inevitable that the EO in question was going to prompt court challenges.
A judge’s job is not to promote the national security of the United States, at least not primarily; judges are there to provide justice to the parties who appear before the court. They take this responsibility seriously, and they are working in a tradition that treats the government like any other litigant, entitled to no special treatment (other than any preference the law prescribes in statutes and precedents). In my experience, the greater the difference in relative power between the litigants — e.g., the mighty government versus a poor alien who doesn’t grasp the legal system and might not be entitled to counsel — the more federal judges bend over backward to ensure that the alien is getting due process.
Let’s say the Trump administration had announced its new policy and explained that it would be implemented beginning one week from the date of the announcement. The ACLU & Co. would still have stormed immediately into court . . . but they wouldn’t have done so while representing highly sympathetic clients who were being detained at the airport amid swarms of protesters, news media, Democratic politicians making welcome-to-Nazi-Germany speeches, and so on. A week’s delay would have convinced most aliens not to travel here and risk detention or exclusion.
The ACLU lawyers would have been trying to conjure up doom-and-gloom rhetorically but without flesh-and-blood horror stories. The government lawyers would have been citing their strong precedents. The judges would have been hesitant, even if they thought the policy was wrong, to take action under circumstances in which the government was on solid legal footing, the courts’ jurisdiction was questionable, and no one had suffered real harm. Meantime, the chance that the policy would result in sympathetic victims would have diminished to near zero: A week’s delay would have convinced most aliens not to travel here and risk detention or exclusion; and any aliens who came would have been doing so in knowing defiance of the EO, not in innocent reliance on the prior issuance of a visa.
Instead, the Trump administration must now litigate on the defensive. Some judge offended by the application of the order to LPRs may decide that LPRs are so woven into the fabric of our society they must be treated as citizens — and if that were to become settled law, it might later hurt the government in cases where there would have been investigative advantage in an LPR’s not being a citizen. Another judge offended by the callousness of giving people a visa and then pulling the rug out from under them once they get here, may decide, “I want to explore whether a visa is the legal equivalent of a contract that the government has breached.” Any of the judges inclined to entertain novel legal claims could order hearings — demanding testimony or answers from government attorneys about how the EO was formulated, which officials were consulted, what preparations were done, whether there are communications between officials about denying aliens entry after they’d been granted visas, and why, if we’re worried about the terrorist threat, Yemen is on the list but Saudi Arabia isn’t, and so on.
If you didn't follow his reasoning, here's the TL;DR version
It's not surprising that, with lawyers representing actually harmed people in court, that there was a judge (I think we're up to two now) who would issue a stay.