I agree with hotpaw2, and often start out at the whiteboard. Specifically, I tend to draw lots of boxes, arrows and lines, interspersed with some acronyms and the occasional key word. This is not meant to make a detailed design, or even necessarily to describe my ideas to a colleague, but to get an idea of what action flows are relevant, and what pieces of information are needed at each step, at a more detailed level than the specification from the stakeholder. Many times, this involves several rounds of erasing and drawing, and sometimes going it over with a colleague, but towards the end I have an idea of what the finished code actually needs to do.
Given this, it's usually pretty clear what data structures are useful. So I need a few bits of configuration data from somewhere (anywhere)? That's a Configuration class holding those right there, and maybe a ConfigurationProvider or similar to populate it. Corresponding interfaces to aid testing, even if I don't have the time to write unit tests up front. Customer details? It's the same thing. Once I am mostly happy with how it has all turned out in theory, I might copy it to more permanent storage, usually in UML or a UML-esque notation in my notebook (if it is only for my own benefit, no need to get too elaborate - at my current job, class diagrams are rarely called for, but action and component diagrams are very useful). For a project I am working on now, one major part of the design took shape on the whiteboard long before I started implementing it, based on a rather vague statement of intent in the specification.
Only once I have the data structures and action flows down do I start thinking in terms of the concrete implementation: methods, entry points, specific data flows, and so on. Usually it's not before then that I even open up an IDE.