It's kind of a complicated question, because it depends on your skills. I personally generally begin with Kubrick (the default theme) and then begin heavily modifying the CSS. To really make a design work, you may have to hack the templates as well to insert classes, rearrange the generated HTML etc.
You could spend time looking through existing WP themes to see if there's something that seems similar enough to start with. I usually stick with starting off with Kubrick mainly because it's a well-thought out theme that has been vetted through several versions. But by the time I finish with it, there may be very little of the original CSS.
You're going to have to just dive in and learn as you go.
PS In the design you link to, that fixed height DIV with the scrollbar for the content section is very annoying from a usability standpoint.