One way I’ve done this is I first make a static web page using html5 and css3. I also layout images and placeholders for video. I add the navigation too.
Then I switch the .html files to .php files. I will start separating the static code into the WordPress template files. I make sure to add quite a few actions and filters where appropriate. I document all of these so I can give a list of them for plug-in developers.
As quickly as possible I try to get an activiatable theme and continue to add widgetized zones.