Short Answer: In the US, laws regulating land use are detailed and varied, even on Public Lands. Check with the local land agency before "roaming."
Loosely you can divide open space in the US into two main categories: Private and Public.
Private Land: The laws governing private land vary by state. In Texas, for example, a landowner is well within his rights to shoot trespassers that he "reasonably feels" are threatening him, or his property. (Known as the Castle Law - as in a Man's Home is His Castle).
Property lines becomes hazy with regards to river right-of ways (canoeing / kayaking) with some areas defining public right-of-way as the waterline, others as the flood-line. In general, as long as you stay in your boat, you should be able to pass through private land, but you might not be allowed to fish from their banks.
Public Land: The rules concerning public land vary between agencies. State Parks, State Forests, National Parks, National Monuments, National Forests, BLM (Bureau of Land Management) Land, National Wildlife Refuges, National Grasslands... etc.
Even Within each of these, there will be differences in what you are allowed to do. Wilderness, Primitive, Roadless are some of the different sub-sections you might find within a single National Forest, or National Park or BLM Land. Most regulations regard the usage of vehicles (where you can and can't drive) and camping. But some rules apply to hiking as well.
The most restrictive are usually National Parks and Monuments - which often have permit systems for overnight hiking, and designated camping areas.
National Forests vary widely on whether you need a permit or not, especially concerning Wilderness areas, which might limit usage / group size to protect the resource. These might also include where you can camp (distance from bodies of water) whether you can have camp fires, etc... or even whether you need a permit. These regulations vary by National Forest.
Generally, however, on non-Wilderness, National Forest or BLM land, you are free to travel on any established, marked road, and camp in any established dispersed camping area (ie, one already barren and obviously been used for camping).
Limits on how long you are allowed to stay exist (usually 14 days).
Conclusion: The US has an awesome system of public lands (quite possibly the country's most redeeming property). However, the right to roam (or the regulation against) varies widely. Check with the local Public Land's office when you arrive in an area to determine what is or is not allowed. (And why... Surprisingly, most of the rules are in place to help protect the resource from over-use, not to ruin your trip.)
As for whether these rules are a "bureaucratic formality": No. Ignoring the regulations are a tickit-able misdemeanor that carries the same weight as a traffic violation, punishable by fines and jail time. In reality, most carry a modest fine, but failure to pay can result in your arrest.
And, as is the case with all laws in the US - Ignorance of the law is no excuse for violating it.