Here's a few tips I like to follow myself!
If you want to make sure your story is off to a good start, plan most of your characters/storyline beforehand. It doesn't have to be in full detail yet, just make sure that you have a guideline you can follow while developing your game, it gives you grip on what should come after one and another event. Like Cyaloom said, write down every idea you may come up with and see if you can do anything with it.
If you're looking for software to make sprites with, GraphicsGale is the best free software that you can get to make sprites, but you can also use Photoshop or any other programs that support transparency and have a Pencil tool built in (I use paint tool SAI but honestly, it's not that suitable for spriting. It's that I'm used to working with it that I'm using it.)
Working with iterations is normal, so don't feel bad if you end up redoing a thing multiple times! It can only get better anyways, so there's no shame in i.e. having one sprite for a character in the first version, then have an updated version in the next because you're not satisfied with the old one etc etc.
For general design, make sure to know what audience you're targeting so you don't start writing things or make design choices that may seem weird for the audience that you're aiming for. If you're going for a casual game make sure that the difficulty isn't too hard and the story not TOO complicated to follow (it still should be a good one though), if you're targeting a more mature and experienced audience like reborn's it's probably better to pitch up the difficulty as well as the complexity of the story (but don't make it too complex or else it'll get confusing, so be careful!).
Lastly, be sure to have fun while making your game! It's important that you're the one having fun making the game because if YOU'RE enthusiastic about your game, it'll rub off on people and they'll get excited with you as well, so enjoy yourself! Storywriting and game development is fun, but of course, don't overwork yourself or you'll end up getting burnt out, which is something you definitely don't want to happen.
Hope the advice helped and good luck! :]