The natural numbers are well-ordered without the axiom of choice. In fact they still serve as the definition for countability without the axiom of choice assumed. Therefore the basic things we know about the natural numbers hold regardless to the axiom of choice. In particular $\mathbb{N\times N}$ is still countable, and $\{A\subseteq\mathbb N\mid A\text{ is finite}\}$ is also countable.
However when the axiom of choice is negated some other weird things could happen in the power set of the natural numbers, and in other infinite sets:
- There could be a set which is infinite, but has no countably infinite subset.
- It could be that there are no free ultrafilters on the natural numbers.
- It could be that the power set of the natural numbers cannot be well-ordered (it can still be linearly ordered, though).
- Countable unions of general countable sets need not be countable.
- It is possible that there is no linear basis for $\mathbb R$ over $\mathbb Q$.
Let us focus on the first one for a moment, such sets are known as infinite Dedekind-finite sets. Their existence contradicts the axiom of countable choice, so if we assume that we can prove that every infinite set has a countably infinite subset. The fourth one has the same properties, it negates the axiom of countable choice.
Both the second, third and fifth points, however, are compatible with countable choice.
As for why we accept the axiom of choice, historically we did not accept it. People found its consequence strange (regardless to the fact they have used it intuitively). After it was proved that assuming the axiom of choice does not add inconsistencies to ZF, people began using the axiom of choice more and see its wonderful applications. It simply made things easier.
For more reading:
- Advantage of accepting the axiom of choice
- Motivating implications of the axiom of choice?
- Advantage of accepting non-measurable sets
- Why is the axiom of choice separated from the other axioms?