To give your question more context, let us remember what Ousterhood is trying to explain in the section of the book. Let me cite the first sentence from the paragraph where you got your cite from:
For the purposes of this book, a dependency exists when a given piece of code cannot be understood and modified in isolation; the code relates in some way to other code, and the other code must be considered and/or modified if the given code is changed.
Then he gives a few examples, and one example is "two pieces A and B of code, where A calls a method from B".
Now to your question:
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.
When the signature changes, you clearly have to change the callers.
When the implementation changes, you may have to test if caller(s) now behave differently, maybe you have to change them as well, maybe not, but at least you have to consider it.
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. Nevertheless, this is usually true, the implementation of a method depends typically on its signature. Sure, there are edge cases where parameters are superfluous and an implementation will not have to be changed when a method's signature changes, but at least one has check whether this is the case or not.
Note the chapter is about "Causes of complexity", which gives some examples how complexity is introduced into a software system by dependencies - even unidirectional oneson a broad scale. 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.