People usually started by simply adopting the new surname informally, often followed by their original surname in parentheses, until their new surname becomes better known among the public—e.g. David Ben-Gurion (né Grin). Then after a year or two, they made it official by registering it at the Ministry of the Interior (or its equivalent during the British Mandate period). This was useful, as in some cases the user might decide to change the name to something else, or to tweak it (as happened in my own family).
In most cases, the Hebraisation was done by choosing a Hebrew name that is similar in sound to the original—e.g. Peres instead of Persky; Lapid instead of Lampa. Some were lucky, and were able to be clever about it: Isidore Roth became Izzy Dorot—thus managing to retain the sound of his birth name.
In other instances, the Hebrew equivalent of the original name in terms of meaning was chosen—e.g. Harpaz for Goldberg. Others crafted a new name from their original initials—e.g. Shne’or Zalman Rubashov became Shazar. Still others just chose a Hebrew name that they liked: Yigal Feikovich, for example, became Yigal Alon.
In 1944, the National Committee (pre-independence precursor of the Israeli government) appointed someone an official organize Hebraization of surnames on a national basis. It became the patriotic thing to do. People who couldn’t decide were given help. The writer Yitzhak Auerbuch was told to contact the Jewish National Fund, who suggested Or-Paz—he accepted.
In 1948—at the height of the War of Independence—the Israeli military launched a campaign for all its soldiers to change their foreign names for Hebrew ones. Senior military officers, judges, diplomats, and other Israeli representatives overseas were particularly pressured to Hebraize their names. In 1955, Prime Minister Ben-Gurion made this mandatory for all officers of the rank of Lt. Col. and above.
In some instances, the Hebrew name was imposed on the person, unbidden. In the 1950s, new immigrants often found that they were simply given a Hebrew first name instead of their foreign one by immigration officials on arrival in Israel—thus, Layla became Leah; Franz became Efraim; Irwin became Aharon.
Once registered at the Ministry of Interior, the new surname becomes official, and is automatically disseminated throughout all government ministries, banks, and other public institutions (unlike, say, Canada, where the user then has to approach each individual institution and show the official name-change document, to get them to change).