Was it built over previous roads? Due to less population was it easier to claim land? Were there disgruntled land owners that refused to sell their land and roads were forced to be diverted?
Also, I'm not sure if I can ask this since this is speculation about the present, but would a project like this be feasible in modern times?
The land surrounding Interstates are owned by the states themselves, from the time of construction through to the present day.
Prior to construction:
Once the detailed designs were complete, officials purchased the land needed for the Interstate. This involves negotiating with the current owners of the land and the people who live on it or have businesses on it. Often, negotiations go smoothly, with agreement reached on fair payment.
If an agreement isn’t reached, the State goes to court and asks a Judge to approve a takeover of the land for the public highway. They do this via various eminent domain laws, most of which are still used to this day for public works projects, easements, etc.
Most stretches on the initial 1920-30s interstate systems simply replaced existing roads or followed adjacent rail lines, with the initial plans drawn up in the "Pershings Map" and the 1921 Phipps Act creating initial funding (expanded tremendously during the Eisenhower/ww2 era).
Since colonial times, the power of state governments to expropriate land for public purposes has been unquestioned, and this power is both recognized and limited by the Fifth Amendment. Much of the needed land was in fact taken through eminent domain proceedings. This was less common in western states, because so much land in unpopulated areas is owned by the federal government, which happily transferred the needed right-of-way to state highway departments.
Procedures vary somewhat from state to state, but in general, if the landowner is not satisfied with the price being offered for the property, he can ask for a judicial proceeding, at which evidence from appraisers will be offered to determine the property's "fair market value." Incidentally, many states also give eminent domain authority to private companies providing a public service, including electric and gas utilities, railroads, and pipeline companies.
Landowners can't hold out against the state and force diversion of highways, but there were prominent instances of superhighways cancelled or rerouted because of local protests and political maneuvering. Much has been written about the freeway rebellion, including the books Superhighway: Superhoax, Rites of Way: The Politics of Transportation in Boston and the U.S. City; and chapters in Divided Highways and Earl Swift's excellent book The Big Roads.
As for modern feasibility, superhighways, including segments with Interstate numbers, are still being built all across the US.
I know I keep plugging this book, but it's essential to understanding American midcentury city planning, so I'm going to keep right on doing just that. Of course the book is The Power Broker: Robert Moses and the Fall of New York, by Robert Caro.
Caro analyzes the role that power-politics, and especially battles between "master builder" Robert Moses and household names like FDR and Fiorello La Guardia, played in the major construction projects that continue to define the New York City metropolitan area. Some of the projects he examines at length are the "Northern" and "Southern" State Parkways -- the first multilane, no-stop thoroughfares through Long Island -- the Cross Bronx Expressway, the Battery Tunnel, etc.
None of these are interstates, of course, but the process is instructive. As Caro explains, if you're building a road through an area that has some population, any population, the state has to first acquire the land, called the "right-of-way." As /u/Mycd points out, this can be easy. Sometimes land values are low and sellers are willing to part with them. In other cases, it gets hard. Then, the state can either give up the project, alter it, or "condemn" the land.
[legal background]
As a momentary divergence from Caro, condemnation means legally "taking" real property from the current owner and assigning it to a state purpose. This process is called "eminent domain." The process and legality of eminent domain is controlled in the United States by the Fifth Amendment, which states, among other things, that "private property" shall not "be taken for public use, without just compensation." All of those italicized phrases are subject to litigation. Originally the Fifth Amendment applied only to federal expropriation or "takings" (as they're called), but the Fourteenth Amendment "incorporated," or applied, the Bill of Rights against the states as well. The power has been interpreted expansively, in cases allowing "takings" for the purpose of slum clearing and urban renewal.
[/legal background]
Back to Caro. Starting with the Northern- and Southern State Parkways, the main factor in determining whether the roadways were "feasible" to build was the cost of land. Long Island in the 1920s-30s was split between the mansion-heavy Nassau County, the site of much of The Great Gatsby, and the farther east Suffolk County, which was mostly farms. And, Robert Moses, the then-Long Island State Parks Commissioner and planner behind the parkway, wanted more than a Long Island highway/parkway. He wanted a road that connected the island to the City. To realize that goal, his road would have to be built upon land in heavily-developed Queens, affluent Nassau, and, of lesser concern, modest Suffolk.
On the Southern State Parkway, Moses got lucky. He discovered that Kings (Brooklyn) County owned a watershed area rendered unnecessary by subsequent development, which just happened to connect directly from the city's heart into Nassau County. Since that land was already state-owned, all that remained was for it to be assigned to the highway project. It was.
On the Northern State, Moses brokered an intricate string of deals under which the right-of-way would be acquired through condemnation from wealthy Nassau landholders at lower cost, in exchange for diversions around (or through disused portions of) the grounds of the seller's mansions.
Both parkways would run into problems, though, where they abutted (or plowed through) country clubs or other affluent and indivisible areas, such as a duck-hunting preserve near Oyster Bay, Nassau County, where Moses's highway was briefly stopped when interested, wealthy landowners sued to keep their park inviolate. Caro chronicles at length, and critically, the ultimately successful but (he claims) ethically ambiguous way in which Moses cut through the resulting lawsuit. Moses's attempt to undervalue the land, to make its acquisition through condemnation feasible for the mostly-broke state government where otherwise it would not be, was a stumbling point. Later, a single landowner on Fire Island would force Moses to cancel a planned extension of the Southern State running through it and connecting Montauk.
There's much more to this story. When Moses built a highway through the densely inhabited South Bronx, for example, Caro argues he ruined lives. If you have a New Yorker subscription, some of Caro's history of the event is in the July 22, 1974 issue.
In summary, highways have to be built on land. The state acquires land through eminent domain. Where major public works are planned, like highways, that gets expensive and destructive.