Can the president order the construction of a wall in the southern border just by himself, such as with an executive order?
What kind of approval does he need to initiate construction of such a wall?
The main problem is getting the money from congress.
The US executive has a budget plan which is made by Congress. This budget plan says how much money the President is allowed to spend for what purpose. Building a border fortification requires labor and material, and unless Trump can somehow find a way to get someone else to pay for it (good luck with that), these must be paid from the federal budget allocated for this purpose. Fortunately for Trump Congress decided last year to allocate $1.6 billion to improving border fortifications. Unfortunately this is still short of the $2.6 billion the Department of Homeland Security requested for this purpose.
If the Trump administration can somehow finance the construction, there might still be some minor local problems to solve. For example there are some environmental concerns. Improved border fortification doesn't just prevent people from migrating but also blocks the natural migration paths for animals. Environmental protection groups might go to court over this. Also, the building plans might interfere with local property rights. The US government can't just build fortifications on land owned by private people. When the owner doesn't want to sell, the government would have to try to acquire the land with eminent domain power. But when the owners are willing to put up a fight, this might require a lengthy lawsuit. At least one group is planning to exploit this to oppose Trump's border wall project.
In addition to money, property rights will be an issue.
In most parts of the country, the land is either privately owned, national/state park, or Indian land, right up to the line. In fact, in Arizona, one Native American tribe, the To'ono Odham, extends across the border into Mexico.
One of my neighbors owns border farmland. He told me that under Roosevelt, the Federal Government used eminent domain to secure a 60 foot wide easement coast-to-coast along the border, including across his land.
Recently, several media outlets have reported that Department of Justice is in the process of massively ramping up eminent domain processes along the border, so my assumption is that the government will try to either outright seize the properties, or vastly expand the width of the easement.
One area that will likely not be a problem is environmental reviews. With the RealID Act, Congress gave DHS the power to waive most laws, including environmental laws, that could slow down building the border fence.
This was very much a bipartisan law. The original RealID law was passed under George Bush in 2005, and
That power was further expanded under Obama in 2013.
Update: accepted suggested replacement of Indian with Native American.
I had originally avoided "Native American" because this is a US-centric term that seemed inappropriate for a tribe that is at least partially in Mexico. For lack of a more comprehensive term, I had used Indian. On second thought, neither term seems particularly fitting.