My approach to multi-threaded debugging is similar to single-threaded, but more time is usually spent in the thinking phase:
Develop a theory as to what could be causing the problem.
Determine what kind of results could be expected if the theory is true.
If necessary, add code that can disprove or verify your results and theory.
If your theory is true, fix the problem.
Often, the 'experiment' that proves the theory is the addition of a critical section or mutex around suspect code. I will then try to narrow down the problem by systematically shrinking the critical section. Critical sections are not always the best fix (though can often be the quick fix). However, they're useful for pinpointing the 'smoking gun'.
Like I said, the same steps apply to single-threaded debugging, though it is far too easy to just jump into a debugger and have at it. Multi-threaded debugging requires a much stronger understanding of the code, as I usually find the running multi-threaded code through a debugger doesn't yield anything useful.
Also, hellgrind is a great tool. Intel's Thread Checker performs a similar function for Windows, but costs a lot more than hellgrind.