My understanding is hazy, but I've been told that to get from certain parts to others, like Jerusalem to Bethlehem, you may need to cross non-Israeli-controlled areas. Does this mean you'd need your passport and a different visa, or can you just cross through these zones if you're not from the area (ie just a random tourist from far away)?
You can just cross through these zones. No extra visa required. There may be checkpoints where the Israeli army will have a look at your passport or scan your bags (such as e.g. the Bethlehem checkpoint). But on some road blocks they may just wave you through (such as e.g. on the road 90 in the Jordan valley). It all depends on the current situation ...
In any case, take your passport.
All this is true for the West Bank. Gaza is a different matter. But anyway the random tourist from far away does not want to go there.
It is also worthwhile to know that the biggest part of the West Bank remains under Israeli control (see below). The city of Bethlehem is for instance one of the few places under full control of the Palestinian authority (Area A) whereas East Jerusalem is under full Israeli control (Area C).