I have always found, the earlier you start playing with prototypes, the more iterations you get and the better the product.
Start with the background work (market analysis, competition evaluation, target audience, specs sheet, etc.)
Start sketching - low fidelity mockups (paper, balsamiq, what have you)
(and 4) High fidelity mocksup (near pixel perfect layout designs) - Once you have a feel of what your requirements and deliverables will be (even if its a personal project), jump into prototyping. Make simple linked pages to see if the navigation makes sense, see if you have enough real estate to fit all the elements.
Make changes to the existing design, reiterate the mockups and the prototypes till you are finally confident that you have almost everything ready. Then dive into actual application development.
Polishing bugs, last minute changes, etc.
Remember, 'Fail early, fail often.'