The first tool I use that works really well is simple pencil and paper prototyping. Draw a UI, and then put it in front different people and pretend it's the actual interface. Have some try to figure out the what and how with no guidance, and with others start by asking them to complete specific tasks. Ask them what they think particular affordances might do before they click on them and speak about what they're thinking as they click around. You can even respond and quickly doodle fixes and ask them if that improves things. This is the cheapest and fastest way to getting a working UI I find.
The second tool I use for quickly understanding how to block out an interface is largely derived from the book Designing from Both Sides of the Screen. It's a spreadsheet to generate a frequency by commonality grid. Create a spreadsheet with these columns:
"Task name" "How often" "How many people"
Identify all the tasks the user must perform to use the application and put them in the first column, then fill in how often users perform it, e.g., "daily", "occasionally", "seldom", using frequency terms that make sense for your app, then fill how out how many people would perform the task, e.g., "everyone", "most", "few". Then create two axes for a graph: frequency and commonality and plot the results. You'll quickly identify those tasks that are done frequently and by everyone as items that will need to easily accessed globally within the app, and those that are done "seldom" by "few" hidden several clicks away. Furthermore you'll find some items "clump" and get some insight into how tasks can be logically organized.
In my experience there is a third dimension, "Business priority", that can often be at odds with frequency and commonality analysis, so I often add that column and consider this as well. An example of how business priority might trump these other concerns is putting the task of upgrading to a premium subscription much higher in the UI even though it might be done by relatively few people only once. So I advise thinking of this analysis in 3 dimensions. I have found providing this sort of breakdown to a graphic designer to be very well received and a great input to wireframing.
After that, it's measure, measure, measure. Setup analytics with goal tracking, and track your key metrics and regularly schedule sit downs with customers to do usability testing and review as features are added (or removed).
