It’s a little upsetting to see people not realize that Palestinians are, by in large, stateless, which is at the core of the Arab-Israeli conflict. I’m going to tie up a few ends here…
Israel’s population is roughly 80% Jewish, 20% Muslim, and very small percentage Christian, Druze, Baha’i, etc (Hey, I said roughly!). The accepted definition of “Palestinian” includes Arab residents of the land of Palestine (as first definitively defined by the British) west of the Jordan in 1947 as well as anyone (Jews included) who resided in Palestine west of the Jordan prior to 1917 (beginning of the so-called Zionist invasion) and all of their descendants, typically using patrilineal descent.
We should note, for historical accurace, that prior to the British Mandate for Palestine after the fall of the Ottoman Empire, “Palestine” was a region and not a definitve area- saying that you hailed from Palestine was akin to saying you’re from the “midwest” - people would have an idea where you’re from, but few would draw exact border lines for the region on a map. During the reign of the Ottomans, what we’d refer to today as “historic Palestine” fell under control of the Syrian governor. I’m thinking this is where JerseyDiamond got his answer. The idea of “Palestinian” being a distinct nationality really did not come about until Zionism; some people point this out as illegitimacy of Palestinian attachment for the land, however I don’t think that’s fair. Palestinian nationalism came about slightly after Zionism, because only the Palestinians had to deal with Zionists coming to their land and eventually making (most of them) refugees from it. It’s this common experience- being in the land that Zionists wanted- that makes Palestinians a nation as real as any other.
Anyhow, back to history. During the war of 1948, 750,000 Palestinians were made refugees from the war and ended up east of the eventual armstice line, also known as the Green Line. In some cases this came about from being directly deported or ordered to depart, or in other cases the Palestinians fleed after hearing cases (with some truth and with some exaggeration) of Zionist massacres of Palestinians.
If you ended up east of the green line, or in the Gaza Strip, you were a refugee and were stateless. The West Bank and East Jerusalem was claimed (in a move only recognized by Britain and Pakistan, if memory serves) by Jordan in an expansionist Jordanian measure. Gaza fell under Egyptian military occupation, however Gaza was not annexed by Egypt. Jordan offered Palestinians citizenship; Jordan, until the 1980s, did this in an attempt to have its annexation and claims to Palestine regarded as legitimate. If you ended up in Gaza, or in a camp in Lebanon or Syria, you were stateless. If you ended up in Israel, you were given Israeli citizenship, although if you were apart from your home your land was eventually taken from you and leased for Jewish-only purposes.
Now, what else… it should be noted that those who ended up in Syria or Lebanon were not offered citizenship (Lebanon has a delicate ethnic balance and it would send the country into another civil war if such a move ever happened, Syria out of principle) and their children generally do not have citizenship, either. So there is a real problem of totally stateless refugees who wander about the region. To answer your question, they have no passport. They have, if everything works right, Palestinian refugee travel documents. Sometimes they can’t even get those, however, and the question of where to put them or send them is a real question many authorities face. Where do you send a Palestinian refugee when his visa expires?
As for the mass conversion idea, the catch is Israel won’t acknoweldge a conversion unless an orthodox rabbinical court oversaw it, and said rabbinal court checks to see if they’re converting due to spirtual conviction, and if they’re doing it simply to make aliyah and move to Israel, well, it wouldn’t work. I assume being a Palestinian makes it very hard to convert to Judaism, given this.