The game mechanics, the technology or the story (assuming there is one)?
By game mechanics I mean the system(s) used to run the game, the rulesets that determine legal moves, transactions and their results.
By technology I mean how the game is physically modeled, whether that's a set of dice or a PC.
By story I mean any narrative elements assigned to the game elements. Saying that an animated circle is Pac-Man and he chases ghosts is perfectly valid for this argument.
Now, just to be perfectly clear, I'm not going to give any kind of straightforward answer. This is how I cover my ass when I say something contradictory three posts from now. Or a few paragraphs down.
I'm interested in the methods that people prefer.
Myself, I guess I would say, "It all depends." Sometimes I'll get some strange, compelling, kickass game elements in my head and I try and build up something around them. Other times a neat little story will pop up and I feel like it would work well as an interactive kinda thing. Or, y'know, I read about some awesome new 3-d engine techniques and start thinking about how they could lead to fascinating new game mechanics or support a narrative.
So I guess a little of everything.
Some designers definitely seem to favor one section over the others. Carmack obviously goes for the tech stuff first. Will Wright goes ga-ga for interesting little game mechanics.