https://en.wikipedia.org/wiki/International_recognition_of_the_State_of_Palestine
Looking at the map, I noticed that Eastern European countries are more likely to recognize Palestine as a state, than Western European countries, what are the political reasons for why this might be the case? I was thinking it might have been Russian political and cultural influence, but I wasn't so sure.
This dates back to 1988, when the Soviet Union and the "iron curtain" still existed.
At that point, the UNGA passed a resolution recognising a state of Palestine. The Soviet bloc and most of the third world followed suit by recognising Palestine as a state. Western countries mostly abstained (the US voted against, but as this was a GA vote, there is no veto, but the decision is non-binding)
From that day to this, the recognition has not been rescinded by formerly communist countries in Europe, hence these Eastern European countries formally recognise "Palestine" as a state.
I agree with the previous answer that it likely is based on cold war events.
Russian / Soviet support for the PLO and Palestinian cause really date back to the 1970's when the Soviet Union lost influence in the region due to Egypt's Camp David peace treaty with Israel. Egypt ceased as a Soviet client and aligned itself with the West at that point. This motivated the Soviet Union to move beyond contact with the PLO and began to actively support it from that time forward.
Israel's greatest existential opponents over it's short and troubled history were supported by the Soviet Union. Egypt which fought Israel in 49, 56, 68 and 73 all while a Soviet Client state. Syria still a Russian client state fought in each of those wars and in Lebanon in 1982. Israel currently is bombing Syria. That in each of these wars the Soviet Union built and rebuilt it's proxy militaries in each country to be on par or numerically superior to Israel. Israel thus thwarted Soviet military expansion and influence in the region for decades during the cold war.
Other answers point to Cold War politicking as the proximate cause for today's predicament, which is true, as far as it goes. The Iron Curtain was a thing, the US and its satellites recognised (and supported) Israel, and so the Soviet Union and its satellites recognised Palestine (and supported many of Israel's neighbours and foes). This explanation, however, leaves something to be desired. Namely, it obscures Eastern Bloc support for/affinity to Israel and it begs the question of Western support for same.
The known history of the Levant goes back, quite literally, pretty much as far as we have written records, with Western writing having been developed around the corner in Mesopotamia, refined in Anatolia and the Levant itself (with a plausible, though likely spurious, ethno-cultural lineage from the Phoenicians who developed the Abjad to the Philistines of the Bible to the Palestinians of today), and perfected in Greece and Rome over the course of millennia. This is not the history exchange, so we do not need to cover all of this span, but in order to get a fuller picture of the modern geopolitical situation we should turn our eyes to the beginning of the Cold War and the formation of the modern state of Israel.
The first question is, why did the Western Bloc throw its weight behind Israel? The answer is multifaceted, and has elements which tend to upset both supporters of Israel and supporters of Palestine. In short, Israel was established out of the British Mandate of Palestine in the ashes of the Second World War, when a combination of sympathy for the surviving victims of the Holocaust and reticence toward reintegrating Jewish populations into Western Europe and North America led policymakers to embrace Zionism and to establish a refugee state in Mandate Palestine for Europe's surviving Jews.
The Zionist movement was itself a few hundred years old at that point, but had never had more than lukewarm sentiments from the British government before the Holocaust and the post-war refugee crisis -- which included, among other things, resettling over fourteen million Germans who'd been forced from territory in Eastern Europe that their families had settled, often for centuries. In light of these emergencies, establishing a Jewish settler-colonialist project on Europe's periphery on a bit of land Britain controlled seemed like an agreeable solution to preventing a possible second Holocaust. American support for Israel, while not uncomplicated (especially over Israel's nuclear weapons program), was also quite strong from well before the official establishment of Israel as a nation state.
When the Arab-Israeli Conflict really took off (and after British and French colonial power proved moribund in the Suez Crisis), the Americans decided the only way to secure shipping and keep the region at all stable was to play all sides against each other, and it even opposed Israel on several occasions (including during the Suez Crisis itself) in order to try and retain some influence among the Arab states.
The Soviet Union's relationship to Israel is similarly interesting, to say the least. Officially, Bolsheviks opposed Zionism on ideological grounds since before even the Soviet Union came to be; a further complication is that the Soviets declared part of their own territory as the Jewish Autonomous Oblast a full decade before Israel declared its independence.
However, in the immediate post-war period, Stalin and his confederates considered the newly-formed state of Israel a prime candidate for socialist revolution. Not for nothing, millions of Jews from Eastern Europe and the USSR settled in Israel after its founding, which gave a large part of Israel's population pretty significant personal ties to the Eastern Bloc as well -- many Jews remained in Eastern Europe, and remain there to this day. (A prominent example is Ukrainian president Vladimir Zelenskyy, who, likely out of a combination of his own heritage and his country's geopolitical situation, declared unambiguous support for Israel at the outbreak of current hostilities.)
Thus, in practice, the Soviets recognised and had fairly good relations with Israel until the Arab-Israeli conflict brought the Israelis firmly under the American security umbrella and forever closed off the possibility of a socialist takeover. By the time of the UN resolution in question, these lines had been drawn for a couple of decades. But one can well imagine a few decisions or contingencies going the other way, resulting in far less diplomatic support for the Palestinians in Eastern Europe. One may also imagine, as Russia grows ever-more belligerent to recover its influence amongst its neighbours, we see more Zelenskyy-like declarations of support for Israel and possibly a rescinding of recognition for Palestine.
