The vertices of each cell of a simplicial complex are often assumed to have an ordering, for example in these notes, this exercise, and this blog post.
From the ordering of the vertices of a simplex $\sigma$ and the ordering in a face $\tau$, you can calculate the incidence number $[\sigma : \tau]$ between them by evaluating the sign of a permutation.
From the incidence numbers you can define boundary operators on chains and everything you need for homology.
For example, in 2D Euclidean space this means that all the triangles go around counterclockwise.
Many statements about ordering can be turned into statements about determinants of matrices formed from the vertices of each triangle.
The incidence numbers between cell and faces in CW complexes, on the other hand, seem to always be defined through the degree of the attaching map.
There's no ordering assumed at all, but if you can define the incidence numbers then you can also define boundary operators and thus homology.
Is ordering a special property of simplicial complexes?
For example, one could also define incidence numbers and ultimately calculate homology for more general spaces constructed from gluing together polyhedra with arbitrary numbers of faces and vertices.
In every reference I've seen (for example this paper or Rourke and Sanderson, Introduction to Piecewise-Linear Topology) that does so, the incidence numbers are defined through the degrees of the attaching maps and there's no mention of ordering.
Why is that?
Can the incidence numbers be calculated through some ordering of the vertices of each cell and it's merely inconvenient computationally?
Or is there some polyhedral complex for which the incidence numbers between a cell and its faces cannot be recovered from any ordering of the vertices?
My hunch is that ordering is meaningful only for simplices.
The Herschel graph is both polyhedral and non-Hamiltonian, which seems to me to imply that there's no way at all to recover the incidence numbers from any ordering of the vertices.
But I'm not great in algebraic topology so I might have misunderstood everything.
Best Answer
The key fact about an ordinary rectilinear simplex $\Delta=\Delta[x_0,...,x_m] \subset \mathbb R^n$ is that an ordering of its vertex set $\{x_0,...,x_m\}$ determined an orientation of $\Delta$, in such a way that two orderings $x_{i_0},...,x_{i_m}$ and $x_{j_0},...,x_{j_m}$ determine the same orientation if and only if the "change of order permutation" defined by the formula $i_k \mapsto j_k$ is an even permutation.
Now, suppose that you have a simplicial complex $K$ with $0$-skeleton $K^0$. When you choose an ordering of the entire set $K^0$, that determines an ordering of the vertex set of each individual simplex in $K$, which in turn determines an orientation of each individual simplex, which in turn determines the incidence number $\pm 1$ for every pair consisting of a simplex and a co-dimension~1 face, which in turn determines the integer matrices that express all of the boundary homomorphisms $C_m(K) \mapsto C_{m-1}(K)$ in the simplicial chain complex of $K$.
But let's unravel this a bit. You don't need a total ordering of the entire set $K^0$ to do this; there's a lot of wasted information in that total ordering. For example, all you really need is a partial ordering on $K^0$ which restricts to a (total) ordering of the vertex set of each individual. For example, the first barycentric subdivision of a simplicial complex does have a natural partial order of exactly that type.
For a more pertinent example of wasted information, suppose that you choose two different orderings of the set $K^0$, and suppose that they just so happen to have the following property: for every simplex $\Delta=\Delta[x_0,...,x_m]$, the restrictions to the set $\{x_0,...,x_m\}$ of the two given orderings determine the same orientation of $\Delta$ (i.e. the change-of-order permutation is even). In that case, the incidence numbers are identical for the two orderings of $K^0$.
So in that sense, I agree with your hunch: ordering the entire vertex set of a simplicial complex is an artifact special for simplicial complexes, containing lots of extra information that is not particularly useful or pertinent. The key information contained in that ordering, for purposes of computing chain complexes and hence cohomology groups, is the set of orientations, one per simplex, and the set of incidence numbers, one per pair of simplex and codimension 1 face. With that in mind, one can see that this exactly matches the relevant information (for purposes of computing homology) for other types of complexes, particularly for very general CW complexes. As hinted at in my earlier comment, for each cell of a CW complex there are two orientation classes of characteristic maps, and the choice of one orientation per cell determines the incidence numbers (i.e. the degrees of attaching maps, as you say).