Alright, so I think, I figured it out:
The states seem to store the current value of the syndrome, so of $\mathbf{m}=\mathbb{H}y$, where the least significant bit of the state corresponds to that entry of $\mathbf{m}$ with the smallest index that is currently affected by the calculation.
In the example:
From trellis column $p_0$ to $1$:
The structure of $\mathbb{H}$ is such that only $\mathbb{m}_1$ and $\mathbb{m}_2$ can change, if $y_1$ is assigned a value.
- State $00$ means: currently, both $\mathbb{m}_1$ and $\mathbb{m}_2$ are $0$. If $y_1=0$ nothing changes. If $y_1 =1$, then the partial syndrome reads $\mathbb{m}_1=1$ and $\mathbb{m}_2=1$. Thus, we go to state $11$.
From trellis column $1$ to $2$:
Still, only $\mathbb{m}_1$ and $\mathbb{m}_2$ are affected by the assignment of a value to $y_2$.
- State $00$ means: currently, both $\mathbb{m}_1$ and $\mathbb{m}_2$ are $0$. If $y_2=0$ nothing changes. If $y_2 =1$, then the partial syndrome reads $\mathbb{m}_1=0$ and $\mathbb{m}_2=1$. Thus, we go to state $10$.
This corresponds to evaluating $00 \oplus 10 = 10$, where the second column $\left(\begin{matrix} 0 \\ 1 \end{matrix}\right)$ of $\hat{\mathbb{H}}$ is interpreted as $10$ to match the states.
- State $11$ means: currently, both $\mathbb{m}_1$ and $\mathbb{m}_2$ are $1$. If $y_2=0$ nothing changes. If $y_2=1$, the the partial syndrome reads $\mathbb{m}_1 = 1$ and $\mathbb{m}_2 = 0$, which corresponds to state $01$.
From trellis column $2$ to $p_1$:
$\mathbb{m}_1$ cannot be affected anymore, so the least significant bit of the state now stores the current value of $\mathbb{m}_2$ and the second least significant bit the one of $\mathbb{m}_3$.
Though it is still unclear to me why this is done in this manner, I am happy to have figured that the states encode $\mathbb{m}$ with the least significant bit corresponding to the current entry of $\mathbb{m}$.
