Just a comment that it is not just a matter of degree: The $g$ for $f(x,y) = x^2+y^2$ is the same as the $g$ for $f(x,y+x^{100})$, for instance, because $(x,y) \mapsto (x,y+x^{100})$ is an automorphism of the affine plane over $\mathbb{Z}$.

@DavidESpeyer: Part of what I was trying to do was to avoid the implicit choice of ordering of the $n$-element set in the polynomial construction, by making all possible choices. I guess there is also a version of the argument that is kind of between the torsor argument and the polynomial argument, namely to consider the action of $S_n$ on the set of both square roots of the symmetric polynomial $\prod_{\{i,j\}} (x_i-x_j)^2$. This slightly simplifies the proof in the polynomial argument that one gets a homomorphism (and avoids having to order the $n$-element set).

@DavidESpeyer: One could replace the t-word with saying that the action is simply transitive, which might be less offensive to some!

@DavidRoberts: What you want does not exist. Any functor from (finite sets of size $\ge 2$, injections) to (size 2 sets, bijections) maps every automorphism to an identity morphism. For an example of what goes wrong, ask what the functor would do to the composition $\{1,2\} \to \{1,2,3,4\} \to \{1,2,3,4\}$ consisting of the inclusion followed by the transposition $(34)$. More generally, the problem is that every permutation is the restriction of an even permutation on some larger set.

That this is a functor is saying that if you relabel the elements of $X$ using a bijection $X \to Y$, then you get a corresponding relabeling $D_X/G_X \to D_Y/G_Y$ (and that this respects composition, ...) This is clear conceptually since the construction never uses the names of the elements of $X$.

For the sake of others: To say that $D$ is a torsor under $\{\pm1\}^E$ just means that $\{\pm 1\}^E$ acts simply transitively on $D$. The construction of $Sym(X) \to Sym(D/G)$ is conceptual in the sense asked for, that no auxiliary computation is required to verify that it is well-defined or that it is a homomorphism. To me, it is obvious that the construction $X \mapsto D/G$ defines a functor from the category (finite sets of size $\ge 2$, bijections) to the category (size $2$ sets, bijections), and then it is automatic that one gets $Sym(X) \to Sym(D/G)$.

@TimothyChow: If I understand you correctly, you are arguing that certain geometric notions like the notion of orientation of Euclidean space are more fundamental than the algebra currently used to formalize them. Maybe you are even speculating that someday there will be a more geometric approach to foundations in which the existence of sgn is immediate? I do like this line of thought, though I don't know if it will be possible.

@FrançoisG.Dorais: WLOG $X=\{1,\ldots,n\}$ and $\sigma=(12\cdots k)$. If $d \in D$ is given by the standard ordering, then $\sigma d$ is the same as $d$ except that the edges $\{i,k\}$ for $i=1,\ldots,k-1$ have been reversed. Thus $\sigma$ maps to $(-1)^{k-1}$.

@TimothyChow: In your explanation, how would you explain what "rotations of a simplex" are (especially for $n>4$), and how would you convince me that they do not generate the whole symmetric group?

This could be considered the "combinatorial core" of the polynomial argument mentioned by David Speyer. It has the advantage of avoiding "external" ingredients like multivariable polynomials, topology, etc. No computation is needed to construct the homomorphism. (Computation is needed only to check that it is nontrivial, but that is very easy, as explained in the last sentence above.)