I posted the main body of this on a GoodReads author's discussion.
I write fantasy, and I am planning a science fiction story as well.
My process used and refined during the writing of the Gifts of Vorallon trilogy:
Imagine my loose concept--"It's going to be a story about A1 going to B2 and all hell breaks loose until C3 gets F4'd"
I like Shakespeare's 5 act story construction as a loose guideline for the dramatic arc. My take on it is:
1. establish the problem
2. come up with a plan to fix problem
3. Uh oh! The plan fails or compounds the problem
4. pick up the pieces and dig deep for the true fix
5. execute final plan
This is a general dramatic arc for the whole novel or series, but each subpart can also run through a similar or partial treatment.
Coming up with the problem is first, followed immediately by coming up with the final solution, even if a partial fix is all that can happen. I boil both of these down to a simple statement like, problem-The God of Undeath is going to destroy the world and all life upon it. Solution-Use all the power of life that can be mustered to stop him.
I then created the intervening moments with the same level of detail: The Plan-create the hero that can stop the God of Undeath. The Uh Oh-There is another opponent of the hero who must be dealt with first.
The new plan-The hero must gather all the life that remains to have a chance of winning.
Then I work on my characters:
I build up my characters until they are alive in my head, a sort of compartmentalized roleplaying. This involves sketching out their likeness so that I can picture them. To define who they are as people, I need to know how they will react in given situations and how they view the world past the end of their own nose. This takes the form of mental and written notes and an interview process I put them through. My goal being to create an individual who feels genuine, and it is just a starting point because the story will further shape them.
I then write a loose outline that connects characters and events together. They all must grow, even though some are going to grow towards the negative and lose some of what makes them sympathetic to the reader.
It is the characters who really fill in the details as I flesh out the story, they see the conflicts from very different perspectives. In the case of my trilogy, the Uh Oh of act 3 was different for everyone. Even the initial problem was not equally understood by all characters until deep into act 4.
Those of you who have read the Gifts of Vorallon may be scratching your head at much of this, but the story really did come about this way. The complexity is the number of levels each character's personal view.
My current project, The Fire of Falraan is even more driven by the characters and my outline is far looser. It has become a fascinating experience for me to write as I allow the characters to guide my hand. All I have given them is a loose "I would like you all to get to 'here' by the time we're done".