There's a difference between a regular or static website layout and a WP theme where you have to integrate WP PHP functions into the design. As Technokinetics said, there are different stages - there's the visual layout and there's the functional PHP.
For the visual design or non-WP websites (I only did one WP theme so far) I usually start from the HTML + CSS using an HTML editor (there are many good free ones I used over the years - NotePad++, Arachnophilia, HTMLKit and now I'm going to give Nvu a try). If the graphics are more complex or need more experimenting I start with Photoshop. It depends on the type of website - if the emphasis is on usability, like an informational website, I start with the code, if the emphasis is on look I may start with the graphics.
If I start from the code my first step is to decide what basic layout or structure best fits the specific requirements of the website - the header, footer, vertical or horizontal bars, if I need boxes and tables, going to use fixed width or make it flexible (if you use fixed width better make it suitable also for 800x600 resolution since some people still use it), what colors best suit my purpose. I create the basic layout and then work on the details.
If I start from the graphics it's usually because I have some graphical elements in mind that I'm not sure what I'm going to do with or because it's a complex graphical design. So I open Photoshop, create a 1024x800 blank image (800 or more because I want to see what it looks like when I scroll) and start moving my graphical elements around till I get a layout I'm happy with, save the parts that need to be saved as images and recreate the rest with HTML.
For the one WP theme I did so far, first I created the visual layout and then moved the CSS plus some HTML into a WP sandbox theme (Ultimate Diva Sandbox, but the sandbox theme you can find here in the Themes section might be a better choice if you're designing for WP 2.7, except you have to place a visible link to the authors in the footer). With a sandbox you mostly have to edit just the CSS, at worst just make some minimal edits in the PHP.
Now I'm trying to work on a website that will use WP more as a CMS and I need a theme with custom functionality, so I can't use a sandbox. As I'm hoping to use it for more than one website I decided to create a sandbox for myself, that is a theme that will have all the functionality I need with the most minimal design possible, so later on I can integrate the same PHP with different designs. I think it's a good thing to do also for regular WP themes, but then you have to dive into the documentation here and look into functioning 2.7 themes to see how everything works, which I don't recommend for your first theme.
If you're going to design a WP theme from scratch some HTML tags might be more usable than others. For the sidebar it's better to use unordered list (ul and li's) than div's because that's WP default.
The software Steveorevo mentioned look interesting, maybe I'll try them. Thanks :-)