In an answer to another question, Joel David Hamkins claims that the theory of endless discrete orders is complete. He suggested I ask this as a separate question so here I am : how do you prove this claim ?
Clearly the examples he gives show that this theory is not $\aleph_0$-categorical ($\Bbb{Z}$ and $\Bbb{Z}+\Bbb{Z}$ are not isomorphic. To see this, notice that any subset of $\Bbb{Z}$ that is bounded from below is well-ordered, whereas it's not the case for $\Bbb{Z}+\Bbb{Z}$ - I don't know if there's an easier proof).
I suspect that this theory isn't $\lambda$-categorical for any infinite cardinal $\lambda$ (although I'm not able to prove it), so I think that I can't use this method to prove completeness.
I know there are other ways to show completeness such as quantifier-elimination but I am not well aware of these and lack practice so I can't hope to prove it that way (but if you can show me, I would gladly have an answer using quantifier elimination).
So on a side note: what methods are there to prove that a certain theory is complete ?
You're quite right that this theory is not $\kappa$-categorical for any $\kappa$: consider the linear orders $\mathbb{Z}\cdot \kappa$ versus $\mathbb{Z}\cdot(\mathbb{Q}+\kappa)$, each of which is discrete and of size $\kappa$.
As to showing elementary equivalence, note that quantifier elimination won't work here: e.g. the formula "$\exists x\forall y(a<x<b$ but $a<y<b\implies x=y)$," that is, $a$ and $b$ are separated by exactly one point. This formula is not equivalent to any quantifier-free one.
Instead, the right tool to use here is Ehrenfeucht-Fraisse games. It's not too hard to come up with a winning strategy for Duplicator in the game $G_n(\mathbb{Z}, \mathcal{M})$ whenever $\mathcal{M}$ is an endless discrete linear order and $n\in\mathbb{N}$, so they are all elementarily equivalent to $\mathbb{Z}$ (and hence to each other). The key observation is that, in the length-$n$ game, two points that are more than $2^n$(ish) apart "might as well" be infinitely far apart; play with the game a bit and you'll see what I mean.
Incidentally, this argument will show that any formula is equivalent, over this theory, to a Boolean conjunction of $\Sigma_2$ formulas (amongst these are those sentences of the form "The distance between $a$ and $b$ is exactly $n$" for $n\in\mathbb{N}$. So there is a weak form of quantifier elimination here, it's just more complicated than those we usually deal with (quantifier-free and $\Sigma_1$).
This does, however, give a quantifier-elimination route towards solving the problem: adding predicates saying "are exactly $n$ distance apart" to the language, the resulting theory eliminates quantifiers. (Another place where we use this trick is in showing the decidability of Presburger arithmetic.)