Does a method really create a dependency between the calling code and its implementation?
Yes, it does: the calling code becomes dependend on the method - on it's signature as well as on it's implementation. And yes, this is an unidirectional dependency: the called method does usually not become dependend on the caller.
I see how the calling code becomes dependent on the signature, but surely the implementation is arbitrary; it could be unimplemented (ignoring the parameters entirely), and therefore not dependent on the signature at all.
First, this is not what Ousterhout wrote. He did not say "the implementation of a method becomes dependend on its signature", I think you have misread that statement. Second, the implementation of a method is clearly dependend on its signature - think which code you have to change when you remove or change a parameter from the method, not just add it.
Note the chapter is about "Causes of complexity", which gives some examples how complexity is introduced into a software system by dependencies - even unidirectional ones. Saying the "signature creates the dependency" is IMHO just a figure of speech, I would not read this too literally. The dependency is created by the caller calling the callee, and when we read the calling code, we identify the dependency by what we see from the callee: its signature.