I finally found a complete answer to my question. My sequence is not the same thing as the convergents of the standard continued fraction of $\theta$ ; indeed, many terms in my sequence are not convergents and many convergents are not in my sequence. However, the two sequences share near-identical properties as we are going to see.
For any $m\geq 1$, enote by $l_m$ ($u_m$, respectively) the largest (smallest) fraction with denominator $\leq m$ that is smaller (larger) than $\theta$. Thus the set
$\lbrace l_m | m \geq 1\rbrace$ is the same thing as the set $\lbrace \frac{a_n}{b_n} | n \geq 1\rbrace$, and for every $n$ we have $\frac{a_n}{b_n}=l_{b_n}$. On the other side of $\theta$, $u_{b_n}$ can be written as a reduced fraction $\frac{c_n}{d_n}$. It is well-known that
$b_nc_n-a_nd_n=1$. To find the next term $\frac{a_{n+1}}{b_{n+1}}$, we use mediants : let $v_0=\frac{c_n}{d_n}$, and for $k \geq 1$ let $v_{k}$ be the mediant of $v_{k-1}$ and $\frac{a_n}{b_n}$. Then one has $v_k=\frac{c_n+ka_n}{d_n+kb_n}$ for all $k$, and there is a unique $k_n$ such that $v_{k_n} > \theta > v_{k_n+1}$. Then the next pair of near-values around $\theta$, $(\frac{a_{n+1}}{b_{n+1}},\frac{c_{n+1}}{d_{n+1}})$ is exactly $(v_{k_{n+1}},v_{k_n})$. We deduce the recurrence formulas
$$
a_{n+1}=c_n+(k_{n}+1)a_n \\
b_{n+1}=d_n+(k_{n}+1)b_n \\
c_{n+1}=c_n+k_{n}a_n \\
d_{n+1}=d_n+k_{n}b_n \\
$$
which can be rewritten more elegantly as a matrix equality : if we put
$$
K_n=
\left(
\begin{matrix}
k_n+1 & 1 \\
k_n & 1
\end{matrix}
\right),
M_n=
\left(
\begin{matrix}
a_{n} & b_{n} \\
c_{n} & d_{n}
\end{matrix}
\right)
$$
then we have $M_{n+1}=K_nM_n$ for all $n\geq 1$. Also, $k_n$ can be written as $\lfloor \rho_n \rfloor$, where $\rho_n=\frac{c_n-d_n\theta}{b_n\theta-a_n}$. If we put
$$
\left(
\begin{matrix}
a & b \\
c & d
\end{matrix}
\right)
\star x=\frac{cx-d}{bx-a},
$$
then this defines a group action of $GL_2({\mathbb Q})$ on $\mathbb Q$ :
$A \star (B \star x)=(AB) \star x$ for any matrices $A,B$ and any $x\in {\mathbb Q}$.
We deduce
$$
\rho_{n+1}=M_{n+1}\star\theta=K_nM_n \star \theta=K_n \star \rho_n
$$
In other words, the sequence $(\rho_n)$ satisfies the recurrence relation
$$
\rho_{n+1}=f(\rho_n), \ {\rm with} \ f(x)=\frac{x-\lfloor x \rfloor}{\lceil x\rceil-x}
$$
If $\theta$ is a quadratic irrational, it can be written in the familiar "Legendre" form
$\frac{p+\sqrt{D}}{q}$ where $p,q,D$ are integers with $D$ a nonsquare, and $q$ divides
$D-p^2$. Then, by induction, each $\rho_n$ is again of the form
$\frac{p_n+\sqrt{D}}{q_n}$ where $p_n$ and $q_n$ are integers and $q_n$ divides
$D-p_n^2$. So $r_n=\frac{D-p_n^2}{q_n}$ is an integer, and we have
$|q_nr_n| \leq |D|$, $|q_n| \leq D, |r_n| \leq |D|, |p_n^2| \leq |D|+|q_nr_n| \leq |D|+|D|^2$. So there are only finitely many possible values for the pair $(p,q)$, so the sequence $(\rho_n)$
takes its values in a finite set. Since it also satisfies $\rho_{n+1}=f(\rho_n)$, it is eventually periodic. Then $(k_n)$ is also eventually periodic, and it is easily deduced that the vector $(a_n,b_n,c_n,d_n)$ satisfies a linear recurrence relation (for more details see the article linked by Aryabhata in the comments).