Static methods should be fine for multiple threads.
Static data on the other hand could cause a problem because attempts to access the same data from different threads needs to be controlled to ensure that only one thread at a time is reading or writing the data.
Variables declared inside methods (with the possible exception of "captured" variables) are isolated, so you won't get any inherent problems; however, if your static method accesses any shared state, all bets are off.
Examples of shared-state would be:
static fields
objects accessed from a common cache (non-serialized)
data obtained via the input parameters (and state on those objects), if it is possible that multiple threads are touching the same object(s)
If you have shared state, you must either:
take care not to mutate the state once it can be shared (better: use immutable objects to represent state, and take a snapshot of the state into a local variable - i.e. rather than reference whatever.SomeData repeatedly, you read whatever.SomeDataonce into a local variable, and then just use the variable - note that this only helps for immutable state!)
synchronize access to the data (all threads must synchronize) - either mutually exclusive or (more granular) reader/writer
Any public static (Shared in Visual Basic) members of this type are thread safe. Any instance members are not guaranteed to be thread safe.
Edit:
As the guys here say, is not always the case, and clearly this applies to classes designed this way in the BCL, not to user created classes where this does not apply.
It doesn't matter if the method is static or not, what matters is if the data is static or not.
If each thread has its own separate instance of the class with its own set of data, there is no risk of data being mixed up. If the data is static, there is only one set of data, and all threads share the same data, so there is no way to not mix it up.
When your data in separate instances still gets mixed up, it's most likely because the data is not really separate.