I find I often start with a map. Some things I know I need on the map because of how the story is going to go. Then I add other things. Some things on the map will give me ideas about how people would live in a place like that. Then I start developing the culture that would exist there. What do they believe? What kind of shelters do they live in? How do they dress? What are the marriage customs? How do they raise their children? Who's in charge and how do they get that way? How does their economy work?
Sometimes I have to tweak my map and my cultures to work with the story I want to tell. Sometimes, I tweak the story to fit better in the world I've built.
For Dreamer's Rose, I knew what the upper left (northwest) portion of the map had to look like. The rest, I just made up.
But even then, when I saw that part of the map drawn, I learned some new things about how that part of the world would operate.
I haven't finished working out all the cultures, which may be why my progress is so slow on the darn thing. At least, part of the reason.