As the Shor's code is a CSS code, it admits a transversal implementation of logical CNOT. An immediate implementation may perform 9 (reversed) CNOT, by respecting the order of the qubits.
However. Considering the answer to this question, I'm led to think that I may define a better implementation, involving just 3 CNOTs.
Is this possible?
TL;DR: No, it is not possible to implement the logical CNOT on two logical qubits encoded in the nine-qubit Shor's code using three physical CNOT gates.
Let $\mathcal{S}$ denote the stabilizer group of the nine-qubit Shor's code. Let $\mathcal{S}_X$ denote its subgroup consisting of $X$-type Pauli operators. It has four elements: \begin{align} &III,III,III\\ &XXX,XXX,III\\ &III,XXX,XXX\\ &XXX,III,XXX. \end{align} In particular, each $X$-type stabilizer acts the same way on qubits in each of the three-qubit sub-blocks separated by commas above. We define $\mathcal{S}_Z$ similarly and recall that each $g\in\mathcal{S}_Z$ acts as Pauli $Z$ on zero or two qubits in each three-qubit sub-bock.
Suppose $U$ realizes the logical CNOT and can be implemented using three physical CNOT gates (acting across or within the two code blocks).
In order for $U$ to distinguish between $Z_L=X^{\otimes 9}$ and $X$-type stabilizers it must be the case that each three-qubit sub-block of the logical target qubit contains at least one (and hence exactly one) control qubit of the three physical CNOT gates. Because otherwise, if conjugation by $U$ sends $I\otimes g$ to $h\otimes gk$ for some $g,h,k\in\mathcal{S}_X$, then it sends $I\otimes Z_L$ to $h\otimes Z_Lk$ failing to propagate $Z_L$ from the logical target qubit to the logical control qubit.
But then there is a $g\in\mathcal{S}_Z$, acting on the logical control qubit, such that \begin{align} U(g\otimes I)U^\dagger=gk\otimes h\tag1 \end{align} where $h$ acts as Pauli $Z$ on exactly one qubit within a three-qubit sub-block. This operator does not belong to $\mathcal{S}$, so $U$ fails to preserve the code subspace.
I'm led to think that I may define a better implementation, involving just 3 CNOTs.
I doubt that it's possible.
The first obstacle that you will run into is that the support of the two logical observables can't be made smaller than 5 qubits. (The X and Z observable can individually be 3 qubits, but the combination covers at least 5.) Generally you need to involve the entirety of the observables for the operation to work. So this will tend to force you to use at least 5 CNOT gates.
The second obstacle that you will run into is fault tolerance. It's not enough for the observables to undergo the correct mapping, you also need to preserve enough stabilizers to check for errors. Some stabilizers cover 6 qubits, so they individually will tend to force you to use at least 6 CNOT gates.
The main way you could bypass these obstacles would be by doing carefully chosen CNOTs within the code blocks, instead of between the code blocks, but then you need to be much more careful about maintaining the ability to correct errors.
For 5-CNOT connection (and 9-CNOT connection)
$$X_L \otimes I = Z_1Z_4Z_7 \otimes I \to Z_1 Z_4 Z_7 \otimes I = X_L \otimes I$$ $$Z_L \otimes I = X_1X_2X_3 \otimes I \to X_1 X_2 X_3 \otimes X_1 X_2 X_3 = Z_L \otimes Z_L$$ $$I \otimes X_L = I \otimes Z_1Z_4Z_7 \to Z_1 Z_4 Z_7 \otimes Z_1 Z_4 Z_7 = X_L \otimes X_L$$ $$I \otimes Z_L = I \otimes X_1X_2X_3 \to I \otimes X_1 X_2 X_3 = I \otimes Z_L$$
this is logical CNOT (with the second block as control logical).
For 3-CNOT connection $$Z_L \otimes I = X_1X_2X_3 \otimes I \to X_1 X_2 X_3 \otimes X_1 \neq Z_L \otimes Z_L$$ Since there is no connection between qubits 2,3 of block1 and 2,3 of block 2.
