Building on this answer this answer, this can be accomplished by updating the
\alglinenumber command, as follows. This isn't yet an optimal solution, as demonstrated by the last line.
\StateRed $x = 1$
\StateBlack $y = 2$
\StateRed $ z = 3$
\State you probably didn't want this to be red!
This also doesn't work perfectly when adding annotations of non-zero width to the line numbers, as the spacing is affected when going from line 9 to 10 (and presumably 99 to 100, though I have not checked).