Question about a certain coding of rotations

This is true for every irrational $\theta$; the question can be rephrased in terms of Sturmian sequences. Given a sequence $z \in \{a,b\}^\mathbb{Z}$ and indices $i<j$, let $z_{[i,j]} \in \{a,b\}^{j-i+1}$ be the subword of $z$ given by $z_i \cdots z_j$. Let $c(z_{[i,j]})$ be the number of times the symbol $b$ appears in $z_i\cdots z_j$. The sequence $z$ is Sturmian if it is not eventually periodic and if it is balanced, meaning that for every $n$, the quantity $c_{[i,i+n]}(z)$ takes exactly two values as $i$ varies. The usual definition of Sturmian is that $z$ contains exactly $n+1$ distinct subwords of length $n$ (for every $n$), but the two can be shown to be equivalent.

A sequence arises as a coding for an irrational rotation (using the convention you describe) if and only if it is Sturmian; this was shown by Morse and Hedlund in 1940; in fact they considered codings of geodesic flow on a torus, but it is equivalent. The condition $\theta < \frac 12$ is equivalent to the condition that $bb$ appears and $aa$ does not, so let's assume this from now on.

A Sturmian word is a subword of a Sturmian sequence. Let $w$ be a Sturmian word of length $2n$, and partition it into $n$ blocks of length $2$. Each of these is either $ab$, $ba$, or $bb$ (since $aa$ and $bb$ cannot both appear in a Sturmian word). Let $\beta(w)$ be the number of these that are equal to $bb$; then it is easy to see that the number of $b$s in $w$ is $c(w) = n + \beta(w)$. Since $w$ came from a Sturmian sequence $z$, every other subword $v$ of $z$ with length $2n$ also has $c(v) = n + \beta(v)$, and moreover $|c(v) - c(w)| \leq 1$. We conclude that $|\beta(v) - \beta(w)|\leq 1$.