$Th(\mathbb{Z})$ is the set of all closed formulas which are true in the model $\mathbb{Z}$ of the signature $\{<, =\}$
I need to prove that $Th(\mathbb{Z})$ is not countably categorical.
Thinking about that I come to suspect that $\mathbb{Z}+\mathbb{Z}$ (the ordered sum of two copies of $\mathbb{Z}$) is a model of the theory $Th(\mathbb{Z})$.
How do I prove it?
The best way to see that your proposed model is indeed a model of $Th(\mathbb{Z})$ is probably by using Ehrenfeucht-Fraïssé games, but you said in the comments that you didn't know about those.
Here's an alternative idea (which doesn't prove that $\mathbb{Z+Z}$ is a model, but that proves that it's not countably categorical) : add two constants, $c,d$ to your language and look at the following theory $T$ : it's $Th(\mathbb{Z})$ + the following axioms (one for each integer $n$)
There exists a strictly increasing sequence of size $n$ between $c$ and $d$.
Clearly, $T$ is finitely consistent (take $\mathbb{Z}$ and interpret $c$ as $0$ and $d$ as $n+1$ ), so by compactness and Löwenheim-Skolem, it has a countable model. Now this countable model, when restricted to $\{<, =\}$ is a model of $Th(\mathbb{Z})$, and it can't be isomorphic to $\mathbb{Z}$ (the interpretations of $c,d$ are infinitely far apart !), thus proving that $Th(\mathbb{Z})$ is not countably categorical.