TL;DR: It's complicated.
I've been to Gaza once a long time ago, in happier days when Yasser Arafat Int'l wasn't a heap of rubble. At the time arriving by plane was straightforward (buy ticket, fly to Gaza), but crossing by land was complicated even then and has become much worse since. This answer is a synthesis of what I understand from the friend who picked up me up at the time, who's been to Gaza multiple times since then, and two more up-to-date sources, in particular this and this.
First, some broad guidelines:
- Think twice if you want to do this. As far as Western intelligence agencies are concerned, Gaza = Hamas = terrorists and voluntarily visiting there is only one step short of training with the Taliban or Islamic State on the suspiciousness scale. A Rafah border stamp will raise eyebrows when spotted anywhere in the world.
- The border can shut completely with zero notice. If Hamas or one of its buddies chucks a rocket over the border, as they regularly do, nobody's going in or out for a while: maybe days, maybe weeks, maybe months. You've got to be flexible and prepared for failure.
So with the airport gone, there are two ways into Gaza by land:
- The Erez crossing, with Israel. Ever since Hamas took over, this has been basically completely locked down and is not a viable option unless you have some serious connections in Israel (or Gaza). Then again, even when "open" this is a famously painful crossing (3 hours plus is not uncommon), plus you'll also be an object of extreme suspicion when you fly out of Israel.
- The Rafah crossing, with Egypt. Smuggling tunnels aside, this is Gaza's only landline and the focus of the rest of this answer.
So here, finally, is what you need:
- A bona fide invitation from an organization in Gaza that can host you. (Tourism to Gaza is not a thing; for one thing, Gaza's sole decent hotel, the Windmill, was burned down in 2000.)
- Once you have the invitation, you need to apply to the nearest Egyptian embassy for a permission letter for Rafah. This may take several months to process.
- Once granted, you need to get your host to apply on your behalf for a Palestinian entry permit.
- Once this too has been granted, proceed to Rafah, about 6 hours' drive from Cairo.
- Exit Egypt at the Rafah border post. Expect this to take several hours.
- Enter Palestine. Your story and documentation will be double-checked.
- You're in!