I'm not really sure how they did it.
But- I think I have a system worked out now for how I can do it. Basically, I first draw some terrain. The I edit it in certain places so that the player could not possibly cross it. Then I sit there for 10 minutes to a few hours (depending on how difficult it is) trying to think of a way across that uses the games features.
This can get a bit risky though. Any creative sparks inside my noodle have to be tempered with the line "How much extra work is this going to be?"
Then, any ideas I have that are too similar to prior puzzle solutions get the question "How pissed off are your players going to be?" which is always immediately followed, "Well, how pissed would you be?"
The answer is almost always a lot.
So it comes to finding a balance. Obviously, I can't repeat anything (unless I'm doing it deliberately) but I also can't start bringing in ideas that are too different without hugely increasing the workload of everyone on board.
I've lost a lot of paper to scrapped ideas.