The first thing to do is to knock together a reasonable facsimile of the UI as quickly as possible. This can be a paper mock-up (hand-drawn, or screen dumps of various components cut out and taped together). Or if you have a really fast prototyping tool (e.g. Visual Basic) you can use that. You then show this to users, to your engineers, Marketing, and to anyone else who matters. Have them walk through typical product use scenarios. Then rip it up, re-design, test, rip, re-design, etc. until you have a UI design that you know will actually work well in real use. At this point you will also probably have identified common features in your UI which will allow you to get some re-use in both your implementation and your UI documentation (see last paragraph, below).
Now is a plausible time to document the UI design. If you do it any earlier (i.e. before you have a design that's solid), the design will change so much that it will require more time to keep the documentation up to date than was spent writing it to begin with.
If you used some kind of medium to high-fidelity prototyping tool you might simply augment that with paper documentation to flesh out the details of interaction, error conditions, accelerators, tab order, misc. constraints, etc. I find this works pretty well for many types of designs, since engineers can actually run the prototype, get a feel for how it's supposed to work, etc.
If I don't have a mockup, then I typically write a paper UI spec. I will grab screen dumps from a UI builder or resource editor. You can augment these with UI "clip art" (e.g. screen-grabbed bitmaps, hand-drawn graphics, menus done as plain text). Text accompanies these illustrations describing how they work, when controls enable and disable, wheat happens under certain conditions, when confirmation or other dialogs appear, tab order, accelerators and mnemonics, some of the assumptions the design is based on, alternative "fall back" designs for specific features, etc.
The big problem with paper UI specs is that they are a lot of work to keep up to date. In practice most projects let them become obsolete as they near product shipment.
If you're on a big project one thing you can do to minimize UI documentation overhead is adopt a more object-oriented approach. Standardize the behavior of any controls which are used repeatedly throughout the project. For example if your users will be setting dates frequently, or using hierarchical trees, or working with currencies a lot, you can specify the behavior and appearance of these things in detail in one place, and refer to them from other portions of your UI documentation. Likewise you can specify common dialogs independently, and specify standards for layout of dialogs and controls (standard border widths, button sizes and placements, etc.). That way if you need to specify a confirmation dialog, you simply say "put up a confirmation dialog here with this message and this default button", and refer to the standard definition of "Confirmation Dialog" for the details. In practice I find that this saves about 50% of the UI documentation effort and also makes the documentation more maintainable (since it's more modular).