How to express taking the next bit of an infinite string in small-step semantics?
In general, the only persistent pieces information in a deduction rule (like the ones in the wikipedia article) are the variables which are shared between one of the premises and the conclusion of the rule.

So in effect, a findOne function that operates on a given (fixed) string and returns the position of the first bit which is one would have to pass the string to the conclusion of the rule. Thus one possible formulation would be

$$ \frac{\mathrm{findOne}(str)}{\mathrm{findAux}(str,0)}$$

where findAux is defined by

$$ \frac{\mathrm{findAux}(str, n)\quad \mathrm{nextBit}(str)=0}{\mathrm{findAux}(\mathrm{getTail}(str),n+1)}$$

$$ \frac{\mathrm{findAux}(str, n)\quad \mathrm{nextBit}(str)=1}{n}$$

And nextBit is defined by other rules. One often uses pattern notation instead, so if strings of bits are represented $1.0.0.1.1.0.0.1\ldots$ (so concatenation is "$.$"), the first rule would be

$$ \frac{\mathrm{findAux}(0.str, n)}{\mathrm{findAux}(str,n+1)}$$

Note that the free variables $str$ and $n$ are implicitly universally quantified, so the first rule reads


  For any value of $str$, the value of $\mathrm{findOne}(str)$ is the value of $\mathrm{findAux}(str, 0)$.


Having "side conditions" such as $str\in\{0,1\}^\omega$ can clarify, but is usually clear from the context. Note that the $str$ in the premisse and the conclusion are the same, by definition of what a deduction rule is.