This depends on how which fundamental operations and relations you want on the natural numbers to begin with. For instance, if you have at most countably many operations on $\mathbb{N}$, then you can easily get many elementary substructures. Take note that any ultrapower $\mathbb{N}^{\mathcal{U}}$ by a non-principal ultrafilter $\mathcal{U}$ on a countable set has cardinality continuum. Take for instance $(\lfloor nr\rfloor)_{n}/\mathcal{U}$ as $r$ ranges over the positive real numbers. This set will have cardinality continuum. Therefore by the Lowenheim-Skolem theorem, the ultrapower $\mathbb{N}^{\mathcal{U}}$ has many countable elementary substructures that properly extend $\mathbb{N}$.

On the other hand, if you let all operations on $\mathbb{N}$ be fundamental operations and all relations be fundamental operations, then it is possible that $\mathbb{N}^{\mathcal{U}}$ has no non-trivial elementary substructures, and we shall be able to characterize the elementary substructures of $\mathbb{N}$. Let $\Omega(\mathbb{N})$ be the structure with underlying set $\mathbb{N}$ and where each operation is a fundamental operation, each constant is a fundamental constant, and each relation is a fundamental relation. We first take note if $\mathcal{A}$ is a model of $\mathrm{Th}(\Omega(\mathbb{N}))$, then every substructure of $\mathcal{A}$ is an elementary substructure.

If $f:\mathbb{N}\rightarrow\mathbb{N}$, then let $\Pi(f)$ be the partition of $\mathbb{N}$ where $x=y\,(\Pi(f))$ if and only if $f(x)=f(y)$. Let $\mathcal{U}$ be a non-principal ultrafilter over $\mathbb{N}$. Let $\mathrm{Sub}(\Omega(A)^{\mathcal{U}})$ denote the lattice of elementary substructres of $\Omega(A)^{\mathcal{U}}$. Let $\Pi(\mathbb{N})$ denote the lattice of partitions of $\mathbb{N}$. In particular, $\Pi(\mathbb{N})$ is a meet-semilattice. Let $\Theta_{\mathcal{U}}$ be the congruence on the meet-semilattice $\Pi(\mathbb{N})$ where
$(P,Q)\in\Theta_{\mathcal{U}}$ if and only if there is some $R\in\mathcal{U}$ where
$\{A\cap R|A\in P\}\setminus\{\emptyset\}=\{B\cap R|B\in Q\}\setminus\{\emptyset\}$.` Then
let $\Pi(\mathbb{N})/\mathcal{U}$ denote the quotient meet-semilattice $\Pi(\mathbb{N})/\Theta_{\mathcal{U}}$. Let $\mathrm{Fi}(\Pi(\mathbb{N})/\mathcal{U})$ denote the lattice of filters on the meet-semilattice $\Pi(\mathbb{N})/\mathcal{U}$. Define a map $L:\mathrm{Fi}(\Pi(\mathbb{N}))\rightarrow\mathrm{Sub} (\Omega(\mathbb{N})^{\mathcal{U}})$ by letting $L(Z)=\{[f]\in\Omega(\mathbb{N})^{\mathcal{U}}:\Pi(f)/\Theta_{\mathcal{U}}\in Z\}$. Then $L$ is an order reversing bijection, and this bijection restricts to a bijection between the principal filters on the meet-semilattice $L$ and the finitely generated substructures of $\Omega(\mathbb{N})^{\mathcal{U}}$. The finitely generated substructures of $\Omega(\mathbb{N})^{\mathcal{U}}$ are generated by a single element, and the finitely generated substructures of $\Omega(\mathbb{N})^{\mathcal{U}}$ correspond to the structures obtained by going down from $\mathcal{U}$ on the Rudin-Keisler preordering. Every elementary substructure of $\Omega(\mathbb{N})^{\mathcal{U}}$ is obtained by going down from $\mathcal{U}$ on the Rudin-Kiesler preordering if and only if the meet-semilattice $\Pi(\mathbb{N})/\mathcal{U}$ satisfies the descending chain condition. This condition is equivalent to the following restatement: if $(P_{n})_{n}$ is a sequence of partitions with $P_{n}\preceq P_{n-1}$ for all $n$, then there is some $N$ where if $n\geq N$, then there is some $R_{n}\in\mathcal{U}$ where if $A\in P_{n+1}$, then there is some $B\in P_{n}$ with $A\cap R_{n}=B\cap R_{n}$ (do these kinds of ultrafilters have a name?). I should note that the one-to-one correspondence between $\mathrm{Fi}(\Pi(\mathbb{N})/\mathcal{U})$ and $\mathrm{Sub}(\Omega(\mathbb{N})^{\mathcal{U}})$ can be generalized to different kinds of ultrapower constructions and even reduced power constructions including Boolean ultrapowers, limit ultrapowers, limit reduced powers, etc. As a side note, I personally have found this characterization of subalgebras useful for studying things such as the Boolean ultrapower and determining when a Boolean ultrapower is an ultrapower.

For example, an ultrafilter $\mathcal{U}$ on $\mathbb{N}$ is selective if and only if the lattice $\Pi(\mathbb{N})/\mathcal{U}$ has only two elements, and selective ultrafilters are precisely the ultrafilters such that $\Omega(A)^{\mathcal{U}}$ has no elementary substructures besides $\Omega(A)$ and $\Omega(A)^{\mathcal{U}}$. Selective ultrafilters may be constructed using the continuum hypothesis.

On the other hand, if $(P_{n})_{n}$ is a descending sequence of partitions of $\mathbb{N}$, where if $A\in P_{n}$, then $\{B\in P_{n+1}|B\subseteq A\}$ is infinite, then it is easily shown that there is an ultrafilter $\mathcal{U}$ such that $P_{n+1}/\Theta_{\mathcal{U}}\neq P_{n}/\Theta_{\mathcal{U}}$ for all $n$.