What steps should be necessary to optimize a poorly performing query?

1. Look at the execution plan in query analyzer
2. See what step costs the most
3. Optimize the step!
4. Return to step 1 [thx to Vinko]

In SQL Server you can look at the Query Plan in Query Analyzer or Management Studio. This will tell you the rough percentage of time spent in each batch of statements. You'll want to look for the following:

• Table scans; this means you are completely missing indexes
• Index scans; your query may not be using the correct indexes
• The thickness of the arrows between each step in a query tells you how many rows are being produced by that step, very thick arrows means you are processing a lot of rows, and can indicate that some joins need to be optimized.

Some other general tips:

• A large amount of conditional statements, such as multiple if-else statements, can cause SQL Server to constantly rebuild the query plan. You can check for this using Profiler.
• Make sure that different queries aren't blocking each other, such as an update statement blocking a select statement. This can be avoided by specifying the (nolock) hint in SQL Server select statements.
• As others have mentioned, try out the Performance Tuning wizard in Management Studio.

Finally, I would highly recommend creating a set of load tests (using Visual Studio 2008 Test Edition), which you can use to simulate your application's behavior when dealing with a large amount of requests. Some SQL performance bottlenecks only manifest themselves under these circumstances, and being able to reproduce them makes it a lot easier to fix.

Indexes may be a good place to start...

The low hanging fruit can be knocked down with the SQL Server Index Tuning Wizard.