Here's my approach to making a comparatively open-ended, sandbox style campaign. I'll use my current home game as an example.
I knew the players were going to be arriving in a bustling, mercantile coastal city, Nicodranas (I'm using Explorer's Guide to Wildmount), so before the game I came up with a bunch of different story threads. One involved the usual jobs board lead on some work, which might lead to a relationship with a local Archmage who has some jobs that could use doing. Then there are some other events going on that they might notice in the newspaper, or pick up rumours about - a disappearance at the theatre, an attack on some street folk, a stolen relic from a shrine, ta kind of thing.
I don't plan any of these out in much detail. Instead I build out the setting with some interesting locations and NPCs, lots of whom might link to one thread or another. And on the first game in the new setting, the PCs just sort of poke around until something grabs their attention. They are also following up on their personal story, so that can also lead to unexpected events.
Once the players start developing a particular direction, I narrow my attention for the next session. In this case, the PCs wound up taking a job to go help out a village on the edge of the nearby wetlands, which relied on harvesting frogs until some kind of creature had recently started terrorizing the workers. That was all I had going in, so before the next game I came up with an antagonist and gave them some motives: a local hag didn't like the villagers starting to over harvest and hurt the ecosystem of her beloved swamp, so was using her froghemoth to scare them off. Okay, the PCs eventually made their way to her hut and confronted her, sort of haggling but ultimately getting into a fight and killing her beloved froghemoth before she plane shifted and escaped. The party returned to the village to deliver the news but also decided the hag had a point so decided to intimidate the villagers to stop the over harvesting. End session.
So for the next session, I just ask myself, what would the hag do next? She's a hag, so a typical behaviour might be to haunt someone's dreams, slowly weakening them until they die, so that's a decent starting point. But I don't use alignments, so why would she do that? Just vengeance? That's a bit thin, but hags also like to bargain, so what could she get? Plus, the party kind of get bonus points for helping out on the frog over harvesting. So she starts in on the old dream torment gimmick but uses it as leverage to get the party to agree to find her a new pet and help her reunite with her long lost sisters, while one of the party members countered that she also wanted help with a possession issue she'd been having (total player side invention that she'd been hinting at for awhile) and now they are off to find the hag's missing sisters.
Phew. That's a ton of story, and that's only the half of it, but aside from my bread crumbs everything is driven by player choices and NPC backstory. None of it had to happen - I don't have some sweeping campaign narrative, and had the players simply made a different choice at any number of points, the current story would be completely different.
So for me, the key is to not write plots, but to write locations and NPCs with wants and needs, and then see what the players do with it.
