This is an open-ended question. What approaches should I consider?
Your first step is to find and understand the parallelism in your problem. It is really easy to write multi-threaded code that performs no better than the single-threaded code it replaces. "Patterns for Parallel Programming" (Amazon) is a great introduction to the key concepts.
Once you have a workable design, start reading the articles in the "Concurrency" topic in the MSDN Magazine archives (link), particularly anything written by Jeff Richter. Those will give you the nuts and bolts stuff on the threading constructs specific to Windows and .NET. (The multi-threading section in Richter's "CLR via C# (Amazon)is short, but very insightful - highly recommended.)
There are some parallel extensions to .NET that are currently in testing and available at Microsoft's Parallel Computing Developer Center. They have a few interesting items that you would expect like Parallel foreach and a parallel version of LINQ called PLINQ. Some of the best information about the extensions is on Channel 9.
I think we could also include non-.NET-specific approaches to parallel processing if those are among the best options to consider.
If you want to branch outside of .NET there has been a lot of discussion about Intel's Threading Building Blocks which is a parallel library for C++.
There are many options and the best solution will depend on the nature of the problem you are trying to solve. If you are trying to solve an embarassingly parallel problem then dividing and parallelising the tasks will be trivial. In that case the challenge will come in distributing and managing the data used.
Some suggestions would be:
Licensed under cc by-sa 3.0 with attribution required.