A "truth commission"
The refugee problem is multi-layered; some layers are ideological and concerned with basic principles, others are practical. Let's address the ideological first.
Israel must acknowledge its historic responsibility for the creation of the problem. In order to facilitate the healing of the wound, such acknowledgement must be explicit.
It must be acknowledged that the creation of the refugee problem was an outcome of the realization of the Zionist endeavor to achieve a Jewish national renaissance in this country. It must also be acknowledged that at least some of the refugees were driven from their home by force after the battle was already over, and that their return to their homes was denied.
I can imagine a dramatic event: the president or prime minister of Israel solemnly apologizes to the Palestinians for the injustice inflicted upon them in the realization of the Zionist aims; at the same time he emphasizes that these aims were mainly directed towards national liberation and saving millions from the Jewish tragedy in Europe.
I would go further and propose the setting up of a "truth committee," composed of Israeli, Palestinian, and international historians, in order to investigate the events of 1948 and 1967 and submit a comprehensive and agreed report that can become part of both Israeli and Palestinian school curriculum.
The right of return
The right of return is a basic human right and cannot be denied in our time.
A short time ago, the international community fought a war against Serbia in order to implement the right of the Kosovars to return to their homes. It should be mentioned that Germany gave up the right of evicted Germans to return to their homes in East Prussia, Poland, and the Sudetenland, but this was the result of the deeply felt guilt of the German people for the horrible crimes of the Nazis. The often-heard phrase "but the Arabs started the war" is irrelevant in this context.
I propose that the State of Israel recognize the right of return in principle, pointing out that the implementation of the principle will come about by way of negotiation and agreement.
Palestinian citizenship
After the ideological aspect is satisfied, it becomes possible to address the practical aspect of the problem.