As a user experience designer, your first priority is to zoom way, way out to birdseye view and get a good feel for what's going on. That means identifying your market, your users, and your stakeholders. Afterwards, you can zoom back in and start getting detailed.
Before you start
Learn the market
Start reading all about products and services that are like what you need to design. Start following competitors on Twitter, subscribe to their RSS feeds and newsletters, and really inundate yourself in what's going on. Your goal is to be able to answer any questions people will ask of you about the service you're designing. How will it fare against competition? Why are you choosing to approach the problem this way rather than some other way? What can you learn from others' mistakes and successes?
Meet your users
Go out and talk to people who will be using the software. This will be easier if it's an internal app, but even if you're designing for a broad group, you'll gain a lot of understanding from meeting and talking to your audience. First you need to identify who these people are (and are expected to be). Your stakeholders will be able to help here - talk to them and find out what their assumptions are about their expected users and market.
Construct personas that broadly define who you expect to attract to the service. Then schedule meetings with people in those groups. Interview them (informally) to learn what they care about. What are their concerns? Do they use any competing products? How do they feel about those? Doing a survey with a larger group works well too.
Manage expectations
If you have a group of stakeholders, look into ways to organise and prioritise their goals in order to create a loose information architecture with which you can start. There are ways to do this, such as mental modeling or card sorts.
Identify who the "real" stakeholders are and make sure you and they see eye-to-eye on the project's goals and expectations. The biggest reason projects go badly is when you don't manage clients' expectations correctly. Make sure they know what you're planning to do, they understand why, and they know what to expect (and when). Give them clear, measurable milestones you intend to reach.
Read Mental Models for more on mental modeling.
Once you've figured out what to do
Paper prototyping
Once you think you have a good understanding of market, audience and expectations, it's time to take a step into the UI with a prototype. Early on it might be a good idea to just do a paper prototype as you will be able to iterate very quickly and bring stakeholders on board. Schedule a session with some of them and get everyone drawing and thinking visually. How will information be organised? Remember to focus on key usage areas of the service, not the homepage - that comes last and will be a result of all the other decisions you make.
Information architecture
After paper prototypes you need to model your information architecture. How will this service work? You need to express the structure of the service in a language team members and stakeholders can understand. A lot of people use Keynote or Visio to make things visual. The goal here is to communicate and define. Spending time here will help you out a lot later on as it gives you time to really think things through. Don't spend too much time - you need to get into designing the UI fairly soon. But make sure you've loaded the structure of the service into your brain and you can think to yourself "how should X work?" or "do I need Y?" without having to consult other things. Make yourself the expert on the domain model.
Content strategy
You need to know what kind of content goes into this site. Who's responsible? When will it happen? What tone of writing? How are you handling microcopy? Since people come to websites to (mostly) read, this is an important step in the process.
Read Content Strategy for the Web for more.
HTML prototyping
After IA you should make things real as soon as possible. You can do wireframes before this stage, but my recommendation is to get real as quickly as you can. After all, you're creating a user experience, not a bunch of static pictures. Start work on mocking up some screens with HTML prototypes, making sure to focus on flow and state. How do different users experience the service? How do transitions from one screen to the next work? How does the service feel when you click around it? Spend time thinking about copy. What feels right?
Now what?
After these steps you should have a rough demo of what you think the app should be and do. During the way you should also have been in constant feedback loops with stakeholders and users, validating your thinking and making sure you don't assume incorrect things. Your next step is to take the prototype and get usability tests running. From there, you'll have a solid foundation to work from and you can start doing iterative prototyping and continue designing the service until you're ready to let some people start using it. Your focus should be to launch quickly so you get out of the imaginary world of development and put the product in the hands of real people.
