How can the Hadwiger–Nelson problem depend on the axioms of set theory? The wikipedia page on the Hadwiger Nelson problem says the following two things:

The correct value may actually depend on the choice of axioms for set theory.

and

the problem is equivalent (under the assumption of the axiom of choice) to that of finding the largest possible chromatic number of a finite unit distance graph.

Assuming we take the axiom of choice as a given, this latter remark makes the problem sounds like a combinatorial problem - not one that you would expect to depend on foundational issues. Is it really possible that two different models of ZFC could contain distinct finite subgraphs of the unit distance graph?
 A: I believe you are misinterpreting the statement.
Any two well-founded models of ZF with the same ordinals will agree on the finite planar unit-distance graphs, and their chromatic numbers. This is due to the Shoenfield absoluteness theorem. (Actually, much more is true - if I'm not missing something, any two models of ZF with the correct $\omega$ should agree on the finite planar unit-distance graphs and their chromatic numbers.) 
However, the axiom of choice is required to show that the maximum of these numbers is indeed the chromatic number of the plane! In the absence of choice, these two numbers don't have to be the same. 

Here's a sketch of how to prove that the chromatic number of the plane is the maximum of the chromatic numbers of the finite unit-distance graphs, assuming choice. We'll actually prove a stronger result: that an arbitrary graph is $k$-colorable iff all of its finite subgraphs are $k$-colorable (this is the Erdos-de Bruijn theorem).
We use ultrafilters (we don't have to, but they're fun). Suppose $G$ is a graph; let $\mathcal{F}$ be the set of finite subgraphs of $G$, and suppose every $F\in\mathcal{F}$ is $k$-colorable. Fix, for each $F\in\mathcal{F}$, a $k$-coloring $c_F$ of $F$. Now let $\mathcal{U}$ be an ultrafilter on $\mathcal{F}$ such that, for each $F\in\mathcal{F}$, the set $\{G\in\mathcal{F}: F\subseteq G\}$ is in $\mathcal{U}$ (such an ultrafilter exists since the family of such sets has the finite intersection property). 
Now let $\chi$ the "ultralimit" of the $c_F$s along $\mathcal{U}$: for an edge $e\in G$, set $\chi(e)=i$ iff $\mathcal{U}$-many colorings $c_F$ have $c_F(e)=i$. It's not hard to verify that this is in fact a $k$-coloring of $G$.
(Strictly speaking, this only shows that the chromatic number of the plane is at most $k$, but the other inequality is immediate.)
