Here's the standard answer, but perhaps you are looking for something different?

A spin structure on a manifold $M$ is determined by a framing of the tangent bundle $TM$, restricted to the 1-skeleton. (i.e. the framing is only defined on the 1-skeleton.) This framing is required to be the bounding framing on the boundary of each 2-cell (i.e. the framing can be extended to the 2-skeleton). Two such 1-skeleton framings determine the same spin structure if and only if they are homotopic. Such homotopies are generated by local moves which change the framing at a 0-cell and at all of the 1-cells adjacent to that 0-cell.

Kirby and Taylor have a nice paper on low-dimensional Spin and Pin structures -- http://www3.nd.edu/~taylor/papers/PSKT.pdf

[Added later]

(1) As Ryan points out in a comment, making the above idea explicit enough to be implemented on a computer is the point of his paper (which is linked to in the original question).

(2) If you are willing switch to the dual space -- functions on spin structures rather than spin structures themselves -- then there is the following relatively simple description which works in any dimension. Define a ribbon in $M$ be be a 1-dimensional submanifold $S \subset M$ equipped with a framing of $TM|_S$. Consider (finite linear combinations of) isotopy classes of ribbons in $M$ modulo the following three moves.

- If $S$ and $S'$ differ by a framed saddle move, then $S \sim -S'$.
- If $S$ and $S'$ differ by adding a single "kink" or "twist" to the framing, then $S \sim -S'$.
- If $S$ and $S'$ differ by adding/removing a small unknotted circle with standard (non-bounding) framing, then $S \sim -S'$.

One can show that the above vector space is canonically isomorphic to the vector space of functions on (equivalence classes of) spin structures on $M$.

Note that if the three occurrences of $S \sim -S'$ above are changed to $S \sim +S'$, then the vector space is canonically isomorphic to finite linear combinations of elements of $H_1(M; \mathbb Z/2)$, which in turn is isomorphic to functions on $H^1(M; \mathbb Z/2)$. This is the counterpart to the fact that the set of spin structures is a torser for $H^1(M; \mathbb Z/2)$.

The above vector space naturally extends to a (fully extended) TQFT.

3more comments