First off, you need to meet certain requirements:
1. Your not hungry
2. You are focused
3. You have enough time
4. Have enough snacks
5. Have friends to judge or help you with your story
Most people ignore these requirements and many end up with a writer's block.
Moving on.
1. Choose a genre
A racing game does not involve saving the universe or a soap does not involve killing 10.000 monsters.
2. Choose your timeline
When choosing the midevil games you must not end up with starships or galactic conquests. However fantasy games can mostly ignore the timeline.
3. Choose your characters
There are already character creation tutorials but here is a few pointers:
3a. Name
3b. Gender
3c. Age
3d. Likes/Dislikes
3e. Description
Explain your character and define his personality, what is his motivation, what is his history, define WHO your character is.
4. The location of your game
Dont make a summer vacation game in the middle of the snowy mountains, or make a farm game in the middle of a warzone.
5. Take everything in consideration
Read what you wrote at the first 4 points and think carefully. Think of the story, dream of the story, transform those images into words, write those words down on a paper.
6. When you dream is faded read what you wrote.
Mostly you made some simple words like: Love, girls, war, treason, apocalyps.
7. Combine those words into 1 or 2 sentences
Like: I loved girls, but because of their treason a war broke out that unlocked the apocalyps.
8. Explain the sentence
Question yourself about that sentence. Why did you love those girls, how did they betray you, what damage did the war do, what form does the apocalyps take place.
9. Redo the story
Now that you have done the first version of your story start over, read what you wrote and put it into the story. Don't forget to dream your story, as it will open more doors and lead to a better story.