Yo me quedo con mi combinación:
Ywriter ->
http://www.spacejock.com/index.html Está hecho por un escritor, por lo que está pensado para el tema de historias. Se puede poner en Español si eso es molestia para ti.
Con yWriter vas creando proyectos (Libros, o historias para juegos, o guion de peli porno, a tu gusto) y ahí metes capitulos, escenas dentro de capitulos, vas definiendo objetivos, o delimitando acciones por capitulos. El tema de personajes, que veo que te mosquea también, también es util, por que los vas definiendo tambien de una manera bastante interesante.
Vamos, que lo pruebas, y le des un tiempo de aprendizaje decente y ya verás como te convence.
Luego también uso el FreeMind como ya te han comentado abajo, enserio, te echará para atrás, pero en cuanto empiezes a usarlo empezarás a ver su utilidad.
Y para finalizar, buscate un buen editor de texto, por desgracia el Ywriter no tiene uno muy completo y para hacer las versiones finales o de muestra a terceros y tal se te puede quedar corto, yo que se, el OpenOffice que te exporta a PDF, y así completas un buen pack gratuito =D
Eso en cuanto a software, que veo que también lo estais hablando, y luego en cuanto a metodología...ahí ya depende mas de cada uno...mi novia y yo somos bastante antagónicos a la hora de escribir, por lo que eso te deberias de buscar algo con lo que te sientas agusto, tal vez se te da mejor crear cosas por separado y luego unirlas, escribirlo todo según te salga...
Puedes probar a ir, como pones de ejemplo, creando primero una guia general de la historia, e ir profundizando una a una luego cada vez mas al fondo. Teniendo definidos los personajes y lugares de antemano. Sus características, historia, etc.
Si es un juego lineal, tendrás un principio, el nudo y el desenlace, casi de seguro esto, así que elije que cosas acontecerán en cada uno de estos (Ej. El principio es donde el jugador conoce todo, personajes, etc. El nudo es donde ocurren los acontecimientos importantes del juego, robos, asesinatos, etc. Y el desenlace donde se decide atacar la base del malo maloso y comienza la travesía y escalada hasta el final).
Ya lo dicho, vas profundizando en cada cosa y acontecimientos de cada zona, diviendolos a su vez si quieres en otras secciones mas pequeñas, por capítulos, aunque al final no se vean reflejadas esas diferenciaciones, para ti todo puede estar muy etiquetado y demás, como en el teatro =D
Espero que esto, soltado un poco sin explicarme bien, y haciendolo un poco tocho, te sirva un poco.
Bye-nee