<p>This is an open-ended question.  What approaches should I consider?</p>

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
.