Think about character, concept, and plot. The Story Triangle identifies these as the three things that you must keep in mind at all times. When you are conceiving the idea for a story, you have to come up with a new combination of these three things, even if each one of them isn't new. The important thing is that the combination is new. So you can say, "I want a team of robots to rescue a kidnapped heiress in a world where the Roman Empire never fell." Keep in mind, this conceptualizing is a delicate balancing act between bizarre and familiar. If you have a very strange concept, you may want your character to be more familiar, or at least perform the actions of a familar action hero type. If you are creating a new kind of hero, or antihero, you may find that by putting him or her in a more familiar setting will help you highlight the nuances of his or her character more effectively.
Before you start, you should have a general sense of what the payoff to this story should be. The story needs to hit a climax that hopefully encompasses both the necessities of the plot and of the main character. Think about every story as having a logical storyline and an emotional storyline. While the logical storyline may be that, say, the heroes must pick their way across the devilish world of Blaaarg, the emotional storyline will be about the cynical wizard who only trusts himself having to learn to rely on his friends. A climax in which everyone has to do their part while the wizard battles his arch enemy to destroy the great black castle is one that ties up both stories nicely.
Introducing the world, the characters, and the plot can be a tough balancing act. Take care not to rush into things. Is your hero a capable, smart, brave action man? Then he'll have to sail through an opening action scene with flying colors. Don't put him in mortal danger with the wimpy first villains. You have to make sure people know he's awesome before you raise the stakes. Try to make the challenge that he's up against relevant to the plot, and based in the concept. He's going to eventually defeat the ElectroKnight in his underground lair? Then the opening scene he should not be fighting street punks. He needs to fight something pseudoscientific in order to get the readers ready for where the story's going. When you're writing a story, you only get one suspension of disbelief. You use it, then everything has to proceed logically from there. Could be that this is in a galaxy far away, could be that someone was given superpowers. In any case, hit that disbelief here so that no one says, "oh, yeah, right" and throws the book across the room in chapter 6.
As has been mentioned before, while writing, keep in mind the story triangle and relate as many things as possible to plot, character, and concept. Think about all these things as you move the story along. You're going way off the rails if you ignore your concept, or your character, or your plot. You need an challenge for your Warrior Princess of Mars? Don't make it cancer. Need a way for your science hero to get through the vault where the bomb is? Don't just make him so happen to be a safecracker, have him train twenty years to be the best safecracker in the world because his brother drowned while he was frantically trying to free him. Looking for a way for your antagonistic goddess and powerful mortal to fall in love? Don't just make it a dozen roses and a romantic movie-- make them kill her former legions of death and slay her tyrannical father (and save the world) together.
This should be enough to get you started on something that people will call, "derivative," "by the numbers," and "uninspired." Making it good is up to you. Good luck!