Here is some info on travel restrictions in a very specific period.
During the 1948–1959 All-Palestine Government Period (a puppet state of Egypt controlling Gaza) 14,000 All-Palestine passports were issued, mostly to Gazan notables and businessmen, with any Palestinians being eligible (including residents of the Jordanian controlled West Bank). It's hard to say what percentage of the population this was. 1945 figures show 32,250, but this was before the Nakba and the next figure is 100,272 in 1982.
Ahmed Mu-awad, writing in Sarakha Illah al-Sama [Cry to Heaven] states:
"Among the tens of passports that I checked, I foud many with entrance permits to Egypt, and a few with Saudi Arabian permits"
This suggests that entrance to Egypt did not come with this passport, but was often granted by the Egyptian government. The book goes onto state that the passport was not recognised elsewhere. So it would seem that the main function of this passport was admittance to Egypt.