In a pure language like Haskell, all data is immutable and no existing data structures can be changed in any way
Actually that is not generally true. Pure languages use non-strict (lazy) evaluation so the evaluation of potentially all subexpressions is deferred. Unevaluated expressions are generally heap allocated as a "thunk". When required the expression is evaluated and the thunk is mutated into the resulting value.
What strategies and techniques do garbage collectors employ in the face of purity that they wouldn't otherwise?
The only thing I can think of is black holes. I don't recall seeing anything else new on the GC side in the Haskell research papers.
What works very well in an impure language's GC that doesn't in a pure context?
The GC write barrier. Impure languages tend to write pointers into the heap a lot more so they tend to have their write barriers more heavily optimised.
Other GC algorithms such as mark-region are much more viable in the context of impure languages because they can have much lower allocation rates than pure languages.
What other new problems do pure languages create for GCs?
Pure languages are very rare so there is a lot less data on how pure programs use memory and, therefore, you are starting in a worse position when trying to write a GC for a pure language.