As a (non) resident alien in the US, what documents (if any) does one need to carry at all times?
Unfortunately, it's not clear. At least, it's sufficiently unclear that at least one US government agency frequently misrepresents the statutory requirements in official statements.
A few years ago, for example, a Libyan man was detained despite having been granted asylum and showing the officers an employment authorization document (EAD), a document that explicitly satisfies the requirement of 8 USC 1304(e) because it is listed as such in 8 CFR 264.1(b). In response, a US Border Patrol official sent a statement to several journalists that included this incorrect statement (quoted here in a blog post by a US immigration lawyer):
According to 8 USC 1304(e), all immigrants 18 years and older are required to carry immigration documents showing they are in the United States legally. Neither an EAD nor a driver’s license is considered a valid document to satisfy this law.
Not only is the statement about the EAD incorrect, but so is the characterization of 8 USC 1304(e). First, it is not limited to immigrants, but applies to aliens generally, therefore including nonimmigrants. Second, it does not require them generally to have documents to prove their status but only to have an "alien registration receipt card" (which is further specified by regulation at 8 CFR 264.1). Third, it only requires them to have such a document if it has been issued to them, so it does not apply to people who crossed the border without inspection.
The blog post linked above also links to a law review article that describes the incoherent state of alien registration in the United States. The provisions of alien registration and documentation are applied differently to different classes of aliens.
Consider, for example, a tourist. One with a visa has been registered when the visa was issued (8 USC 1201(b)), but the official registration receipt provided in the regulations is the I-94 form. Most nonimmigrants, however, are no longer issued an actual form; instead, there are some definitions at 8 CFR 1.4 that are supposed to support the existence of the I-94 as a virtual "form" that arises from the creation of a database record. To prevent such people from being in violation before they print their own I-94 from the government's web site (which most probably don't know is possible, much less why they might want to do so), the regulations also allow that a passport stamp is a valid registration receipt for nonimmigrants.
The best answer to this question, therefore, is probably that aliens in the US should assess the risks of carrying or not carrying various documents in light of their individual immigration status, likelihood of being subject to immigration enforcement, and tolerance for risk.
A tourist in New York City, for example, faces a much higher likelihood of loss or theft of a passport than of encountering immigration enforcement, since the probability of immigration enforcement is effectively zero. It simply makes no sense to advise such a person to carry their passport at all times without some other reason. Should tourists in New York be advised to print a copy of the I-94 so they can legally leave their passports in a safe place? The likelihood of enforcement is so non-existent that even going to the trouble of doing that does not seem to be justified by the non-existent benefit.
A tourist traveling by intercity bus near the Canadian or (especially) Mexican border is very likely to encounter US Border Patrol and ought to be prepared to meet their demands. Strictly speaking, an I-94 printout is sufficient by itself, but USBP will surely want a secure identification document, so having the passport would be helpful. Without it, there is a greater chance of being taken to the station for identity verification.
I say "near the border" because US Border Patrol largely operates within the zone where immigration officers have greater warrantless enforcement powers, within 100 miles of the country's external border. In practice, the only place I'm aware of these powers being used that wasn't within 100 miles of the Mexican or Canadian border is Florida. Yes, the east and west coasts may be entirely within this zone as it is legally defined, but practically speaking US immigration enforcement does not exercise these powers between Massachusetts and Georgia nor between say Los Angeles and the southern Washington coast.
Someone traveling in Border Patrol's operational area who does not live in the US (or who has no appetite for legal action) should most likely avoid conflict by taking the US Border Patrol's (mis-)characterization of the law at face value, but someone who is prepared to go to court may be inclined to ignore it, provided that they comply with the law's actual requirements. The Libyan man mentioned at the beginning of this answer reached a
$35,000 settlement with the US government.
Students and nonimmigrants in similar status are sometimes advised to carry their I-20 forms or similar. This requirement makes no sense whatsoever given the statute's focus on registration documents, but it does make sense under US Border Patrol's misinterpretation of the statute as requiring aliens to be able to prove their immigration status. So someone with an I-20 is left with a choice: do you comply with the Border Patrol's misinterpretation of alien registration law, or do you comply with the regulation pertaining explicitly to I-20 forms that calls on students to "safekeep" them? As with other cases, this is going to be a personal decision based on your probability of encountering Border Patrol and your personal tendency to lose things. If I were a student likely to encounter Border Patrol, I would most likely carry a photocopy of the I-20 and of 8 USC 214.2(f)(2), the regulation saying that students are "expected to safekeep" the form.
