there seems to be a debate online about whether private methods should be tested or not.
Really? Where is this supposed debate?
If it's part of your software, it needs to work. Usually, that means testing it to make sure it works.
If I have an interface that exposes one method, but that method is quite complex and calls multiple other private methods and also makes use of other objects, how do I go about testing that method?
Step 1 - make it less complex. Seriously. If you find it hard to pull out the different bits to test them in isolation, it's going to be double touch to modify or reuse those different bits in a non-test scenario. Do yourself a favor and clean up the function.
Yes, yes, "but I've done all I can! This is an exceptional circumstance!", I've heard it before... Odds are, it's not really exceptional. So question 2:
Surely I should be testing the smallest units possible, even though many of these will be private methods belonging to the class under test?
Absolutely. But you also need to test the responsibility of the thing that aggregates those private methods together, to make sure it did that aggregation properly to get you your correct result. In an ideal world, that would mean treating it like a black box. Take some inputs, check that the outputs are as expected. In the real world, you'll likely have a lot of inputs/setup - but that's what you get for not simplifying the method in the first place.