Palestinian land was taken by a combination of:
- force (see the many documented cases of forced eviction and
destruction of villages)
- business acumen (buying Palestinian land from rich landlords who
lived elsewhere in the Ottoman Empire)
- refusing to do business with Arabs (letting previously bought property, employing)
unless it was in the interest of the settlement in Jews
For the legitimacy, you need to start by defining legitimate, as some said in the comments.
By what may be the standards of many (if you grew up with "it's bad to take from other people") most states in the world are illegitimate. At some point some group kicked another group out or took control of it by force, sometimes you have to go back to antiquity, sometimes it's more recent (settlement of the Americas for example).
What happened in Israel is a special case. It has to do with almost a century of planning and "lobbying" from Jewish leaders in Europe, and was possible because they are "Jewish" (some Christians thought/think the idea of returning Jews to biblical land is romantic / some more extreme ones believe it fulfils biblical prophecy).
It is internationally recognised on the grounds that it is a "special case". I don't think you would have much success arguing that the same should be done about the USA and the native indians, or Australia and aborigens.
By the standard of world history, what happened in that region is business as usual. By more modern standards, perhaps it shouldn't be happening like that anymore.
Also if you want to take it down to realpolitik, look at Israel's geographical position on the map, try to figure out why some who don't particularly care about the Jews want a "special unwavering friendship" with it. It conveniently splits the Arab world in two, between two/three traditional centres of Arab power (Egypt, Syria, Irak). The presence of Israel in the region may sometimes help thwart Arab attempts at unity (Nasser pan-Arabism), independence from Western imposed policies (Syria, Irak, non-Arab Iran) and helps keep some Arab states in-line with Western interests. It's no secret that Israel has the first or second most competent secret services in the world and they work very closely with the US secret services.
At the end of the day, no state is legitimate or illegitimate. It depends if you can impose your legitimacy or not, and if you have enough special friends who will defend your legitimacy. What matters is how the masses of people perceive you today, not what international lawyers or historians argue about.