There are several ways, but it doesn't really matter.
First there are several ways US immigration can know these things. You might have been on a flight to the country in question. Or the US might find out from one of their intelligence partners. Your own country probably knows you made the visit, if you exited the country on your way there. But that's not the point of the exercise. They really don't care about someone who has visited Syria as a tourist.
The targets of this measure are people that the US suspects of having links to terrorism, but no real evidence. They know enough about those people to know that they have visited the countries in question, so they can't evade the measure by lying. People visiting these countries for legitimate reasons are just collateral damage.
The second point is that if you don't declare your visit on the ESTA, and US immigration knows or find out about it, you are guilty of lying on an immigration form. That's going to get your VWP privileges removed, and make it much harder for you to get a visa in the future. That's just fine by them as it gives them a reason to exclude someone acting suspiciously without needing any evidence of wrongdoing. Lying on an application form is a great way to get yourself in trouble.
Finally you ask "how could the US officials prove one has set foot in those countries". The answer to that is that they don't need to prove it. If they believe that you visited those countries and didn't say so, they can refuse you entry.