Yup allways start script, its tempting to go to visuals very early on but dont, you will waist time.
Come up with a load of ideas, simple premises to begin with. Somthing that can be summed up in a single line.
Once you have a premise you like script out somthing rough, just some simple story beats definning the basic structure and key moments. Show them around and get opinions, once you feel happy with that, flesh out the script properly.
I would advise buying a book on writing for animation, there are a couple out there. There are books on what makes a good short as well. Think about empathy, mood, pace etc etc.
After doing this research alot alot alot on anything that could be usefull to the project and do some rough designs, just somthing that is good enough to read in a storyboard, i tend to refine everything after storyboards completed, i find i usually want to make changes after that stage is compleated.
Once you have the rough design done you can start storyboarding, buy the book shot by shot, its fantastic for laying out your shots. This again is another whole big big topic. But generally start small, think about what your trying to convey at this stage, what do you need to establish what is the center of action.
For storyboarding ill start on postick notes so i can do really rough drawings i can move around freely on a wall.
Once im happy with the roughs ill do it in photoshop for a 'readable version', then ill cut the images togeather in an editing program so i can see if the story flows, also adding rough sounds at this stage.
If that all checks out, ill refine the character and work on shot design.Shot design is perfecting any rough scenes in the animatic, checking rule of thirds, that the eye reads well across the shot etc.
Ill then sketch up orthographics for modelling, research anything that i will need for production so there is no ambiguity.
You can then hit production. Do lots of tests before the real thing, save yourself time in the long run. Do performance research as well, thumbnail out the motions.
For a three minuite short with all original content, looking awesome, it will take you a long while. The last film i did was 5 minuites long, took 6 months and was done by two people. If you want to save yourself the pain, make it SIMPLE
good luck, put WIPs up.
(sorry for repeated info )