When you get an assignment to create software for your department, what do you do to create a really good user interface?
Test the interface against real users, listen to their criticisms, and then judiciously make improvements.
Listen to what your users need and then find genuine new or proven old ways to give them what they need.
If you're new to interface design, start with the articles by Joel Spolsky and the Interface Hall of Shame.
I'd start with paper sketches. Before reading Sketching User Experiences by Bill Buxton, I wouldn't have suggested sketching first. But once we actually did it for a project and made changes to the sketches based on user reactions, the results were a lot better than an approach that didn't use sketching.
The value of the sketches isn't merely that they're easier to change than actual code, it's that they give users something tangible to say yes (or no) to and bring a lot of useful questions to the surface before code is written. Sketching or story-boarding an entire interface makes you think through how you want the application to really work before you've gone down a path with actual code that will be hard to change.
There is no substitute for talking to users when doing interfaces, none. Whatever you do, show the potential interface to the actual users not just their managers!
Have them go through the process they will use to do the work with the existing interface and follow the steps through using the sketches of the proposed interface. Look for areas of improvement, for instance, if they need to enter data from a form then make sure the fields on the interface are in the same order as the paper form, you will tremendously reduce data errors that way.
Talk to them about what annoys them with the current process and where their current delays are and what types of errors inthe data they see. This will tell you some of waht you need to know to avoid making those same mistakes this time.
At this stage a few extra hours interacting with the users can save hundreds of programming hours. This is a task critical to the success of the project.
Users don't know what they want
It's my experience that users don't generally know what they want, even when they think they do. Many good designs have suffered from users saying, in effect: "That's what we said we wanted, but it's hard to do {some critical thing} with it" after they receive a product at the end of a long development cycle.
Try "job shadowing"
If the the system you are creating will be replacing an existing system, try "job shadowing" your future users. Follow them around at work when they use the old system and take careful notes of how they do what they do with it. Ask the users questions about why they do particular things, as a way to find clumsy or missing UI features. Ask the user, when they have difficulties: "How would you want it to work instead of what you are stuck with now?"
Or change your software development methodology to be more agile
You may not be able to change your software development methodology, but if you can, I suggest you investigate using an agile software development approach, for example Feature Driven Development.
Agile development takes work to set up and maintain, and it requires a level of commitment and involvement on the part of the future user. But if you can manage this, agile development allows you to make small (inexpensive) changes to your product, introducing the simplest thing that will work, starting with what is most important to the user, and get quick feedback from the user as to what would be better. This iterative approach ensures that there is never a huge gap between what you are making and what the user expects. Another benefit is that if the project's budget is cut, your users will be left something that works and implements key features, even if the product is incomplete.
Edit:
As Scott A. Lawrence mentions in his comment, it is useful, when iterating GUI design, to use sketches/mockups along with descriptive information from the client about what the feature should do.
See if you can get at least a discussion in with a professional in interface design. They'll know things you won't. It's a big and complicated field, and there's plenty of books on the subject.
There should be some official UI guidelines for whatever platform you're developing on. Look them up. (Consider looking up guidelines for other platforms, as well.) Read articles on sites like AskTog (and Jakob Nielsen's site if this will be on the web). Look at UIs you like and don't like, and try to tell the difference. Learn as much as you can. You won't be able to become an expert in a reasonable timeframe, but you can give yourself a good chance to make a good interface.
Once you have a design, sketch it out on paper and show it to somebody who would use it. (At one place I worked, the analysts would get UI requirements by talking to the users' managers. Ick.) Once you're ready to implement something, do quick usability testing, by asking a typical user to perform a typical task. The things to remember are (a) don't guide the user short of absolute frustration, (b) take good notes (videotaping the session is best), and (c) don't bother with more than three users per version.
For software for internal use, you're not going to have resources to do a really good job, and you really don't need a really good job. Strive for "not annoying"; chances are that's more than they're expecting anyway.
Personally I find the most valuable thing to do is to go to the users where they work and ask them to run you through how they are doing that task currently. What you are looking to do is get enough info that you can be a (junior) user like them. Keep special eyes out for things that are currently awkward or a royal PITA.
What makes this so valuable is that if you just talk to users, they will just want what they already have, but perhaps improved a bit. They usually have no idea what is possible to do with software, what is easy, and what is really hard.
Once you are both a user and a developer, you can see things they can't. You may be able to see ways to restructure the entire process to work better on a computer. You may be able to realise that presenting certian information at different points in the process (or just filling it out for them) will drasticaly improve things in ways they couldn't have imagined.
One example I can give is a project where we were asked to computerize a water valve control panel. The existing panel was a bunch of painted lines (representing the piping) with physical pushbuttons in them controlling the valves that could be opened or closed. One engineer just dumbly digitized this (complete with graphic pushbuttons). Dissatisfied, I spent a lunch hour with a GUI tool making a diagram with actual pictures of valves that switched between open and close pictures, and piping cross-sections that showed empty or filled with water based on the state of the various valves. That was not just a copy of what they had, but far better for visualizing where there was water flow in the system. Unbeknownst to me, there were movements to take the contract from us at the time. When the PE saw the redesign he got all excited and said "This will sell the system!"
There are of course the usual considerations of making common operations easy and uncommon things possible (but not cluttering up the normal interface). But IMHO those are secondary.
When I need to construct a user interface? I personally whine and complain that I'm a developer. Not a designer, not a graphic artist, not a photoshop whiz.
Programming and UI design are orthogonal to one another. Its fundamentally no different from the way that programming and marketing are require entirely different skillsets. Of course that doesn't really stop people from asking me to design UI, and I'll always put something together that looks pretty reasonable. Tips which really help out:
Tuck rarely used commands behind a menu. For example, users are more likely to bold and italicize text than convert it to smallcaps.
Line-of-business apps, data entry apps, or anything with a lot of fields should be navigable entirely from the keyboard. Tab through your UI, make sure the focus progresses through items in a reasonable way. If possible, allow users to navigate using the arrow keys, so that the pushing the down-arrow moves the focus to a control immediately below (users prefer this over tabbing horizontally through lots of controls).
Users don't like having someone watching over their shoulder, so use screencapture or video software to record their interaction. When your user stalls, awkwardly uses the mouse to move between fields, searches for several minutes for a particular function, you know you have a problem.
Users hate modal windows. "All I wanted to do was change my password, why does this modal window lock up the entire app?"
Since your code is invisible in the final product, as far as users are concerned, the UI is the app. It can be occasionally useful to design the UI on paper before you ever write a single line of code.
Too often, dev shops will create a paper UI for v1.0 of their app, but won't bother with mockups for v1.1, 1.2, 2.5, and so on. The end result is predictable: a year and half after you unveiled your beautiful pilot version of the software, your UI has become an unstable mess of cruft and garbage. Its so much easier to change a design on paper than in code, so its very important to document all changes in a mockup before you ever make a modification to your UI.
With that being said, if you want a really stellar UI, you need to convince your boss that application development and user-experience design don't overlap. Developers can't design software, end-users and business-users are paradoxically incapable of designing a decent UI, and your office's graphic designer doesn't know the first thing about interaction design.
Follow Apple's example and hire professional user-experience designers. It costs a little more, but you get a guarantee of quality that you just can't get out of your developers.