Genre and Beginning of Plot
So, there are many ways for writer like yourself and myself begin a story. Some jump right into it, quickly deciding for it to take place in a time and coming up with characters and plot as we go and only having a hint of what was to come or how the characters are to act and how the bad guy is working this out. I started out this way but found it rather difficult to go by it and not have some form of an outline and character bios. It'd be a good idea to start by determining these things.
Genre
First, what kind of story do you want? This will help determine what kind of world you want to make and what kids of things you'd want to include. You wouldn't include aliens in a slice-of-life story and you wouldn't find magic in a science-fiction story. You won't find towering robots in the middle of a medieval village. You can decide to do more than one genre in a story so that the robots wouldn't look too out of place in your medieval village, just make sure that each side reacts accordingly.
Setting
Another good idea would be to find out what kind of world it takes place in. It'll help further determine how a character acts in this world and help shape the plot and give the reader an idea of where they might be: a past world with knights, a modern city, a future that has yet to be determined. A story with historical earth would be difficult since they had different ideals and ways of doing things than we do in modern time but so does stories taking place in the future. Near future would be easy but a farther future, you have more things to play with because you can set it back to a more modern medieval world or have flying cars, just make sure you at least cover why the world is like this a little, especially if it's post-apocalypse.
For different worlds or future worlds, set up rules and social codes so it can determine how the character acts and how society acts in the story. Set up quick histories with war, famine, uproars, and peace dotting up for a good two hundred years in your mystical or different worlds. Future worlds, make sure you set up a quick little history saying what happened between now and then to explain why the world the way it is and give years when each event happened.
The Problems and Conflicts
So, you have an idea of what kind of story you want and what kind of world its in, right? What category would it fall under: Person vs Person, Person vs Nature, Person vs Supernatural, or Person vs Self? Having this and matching it with your setting will make it really click.
Person vs Person is just as it sounds: two people fight over something, just what are they fighting over? It has to make sense with your area and genre. For example: In a modern era, two people struggle to be considered to be President. In a magical world, two mages struggle for the hand of the same man/woman. In the medieval times, a young knight sets out to destroy the dictator ruler.
Person vs Nature would be a survival story instead of a person. Natural disasters like tornadoes, avalanches, and tsunamis would fall under this category. Another thing that would fall under this one would be surviving out in the woods, desert, or tundra with little hope. Person vs Nature would best take place in historical eras and modern time.
Person vs Supernatural is a tricky one but according to me, it would deal with stuff like spirits, anything that isn't part of the natural world of earth, and curse/hexes. Alien invasion could also fall under this category but it's entirely your call. This one would be good for any as long as your "supernatural being" goes with that setting. Spirits are best dealt with the past and aliens are best for future. Both can appear in modern times though but they can also go into the other.
Person vs Self is an internal problem the protagonist deals with. It could be a number of things but this one doesn't tend to have an antagonist. The protagonist could be dealing with their feelings towards a certain person or thing or idea or (arguably) it could be a disease that he or she is dealing with. These can be used anywhere.
