I typically start with mundane technicalities like genre, if it's single player or cooperative, platform, how long the average game session will last, etc. Then I go for a central concept (like "no micromanagement", "you are the Emperor of the Galaxy", "asymmetric gameplay", "historical accuracy of medieval world") and a theme. Then I check if it makes sense market wise and if I can manage it promotion wise (where it will be sold, what the price wil be, what kind of player will play it).
A very important part is the decision what will be NOT in the game (like tactics vs strategy, never both). What will be sacrifaced to make the rest of the gameplay solid. Actually it's far more important than what will be in the game.
Next I try to post about it on some forums. Because I need to persuade people the game will be great I need to write certain things, what I wrote/promised adjusts the game and let me know what's needed to make this game appealing (for example in one game I added "saving princess and slaying dragons" because it sounded cool on the game's description ). These improved the game.
Oh yes, and the most important thing, I set the deadline Without it nothing works