One method is to use quantifier elimination. Note that 0 and $S(x)=x+1$ are definable in $M=(\mathbb N,<)$. The expanded structure $M'=(\mathbb N,<,0,S)$ is a model of the theory $T$ of a discrete linear order with zero and successor. You can show that every formula is in $T$ equivalent to an open formula (it suffices to prove it for formulas consisting of a single existential quantifier followed by a conjunction of atomic formulas and their negations), and this implies that every definable subset of $M$ is finite or cofinite. (And as a bonus, it shows that $T$ is complete.)
Another method is to use compactness. In this simple example, you can just take any elementary extension $M^\*\succ M$$M^{*}\succ M$ and an element $a\in M^\*$$a\in M^{*}$ satisfying the alleged formula $\phi$ defining parity. The function $f$ which leaves $\mathbb N$ fixed and maps everyone else to its successor is an automorphism of $M^\*$$M^{*}$, but $\phi$ cannot be satisfied by two successive elements. In more complicated situations, one may need to take $M^\*$$M^{*}$ e.g. recursively saturated (or saturated in some larger cardinality) to define an automorphism by some sort of a zig-zag construction.
Yet another method is to use Ehrenfeucht–Fraïssé games (these are quite useful for showing undefinability of classes of finite structures, but often come handy in other situations as well). By induction on $k$, show that Duplicator has a winning strategy in $EF_k((M,a_1,\dots,a_n),(M,b_1,\dots,b_n))$ whenever the sequences $\vec a$, $\vec b$ are ordered in the same way, and for each $i,j$, the distances $a_i-a_j$ and $b_i-b_j$ are the same, or they are both large (bigger than $2^k$ or something like that). This implies that a fixed formula $\phi(x)$ cannot distinguish two large enough elements.
