Countability in first-order logic is relative to what exactly? Skolem's Paradox tells us that countability in first-order logic is relative.
Relative to what?
Below is what I've gathered.
Countability it relative to:
1. what a model takes to be $\mathbb N$
2. what bijections between $\mathbb N$ and some set $A$ a model recognizes.
Two examples:  
For (1): Let $$ be a model such that $A$ is uncountable in $$.  We add a bijection between $A$ and $\mathbb N$ to $$ and call this new model $$. $A$ is countable in $$.  As mentioned here.  
For (2): The underlying set of a model $$ might be countable from the perspective of a larger model $$, and so $$ might "see" $\mathbb N$ differently than $$. I'm not sure if I've said this right, but here is a post on this.
 A: I fear I may have confused you a bit, but this is a confusing topic after all, and it can take quite some time to wrap your head around it completely.
First let us establish the following fact. We live in a big big universe. This universe, for the sake of conversation is a model of ZFC. However this universe is not a set, and we do not know any sets outside our universe.
This universe judges with (extreme prejudice) what is truly countable and what is not, what is countable is what the universe know has a bijection with $\omega$ (which in our case is "the true $\omega$").
Suppose that there is a model of ZFC $\mathfrak M$ which is a set in our universe, it may be countable and it might not be. It might know the same true $\omega$, and it might think that some other set is $\omega^\mathfrak M$ (the set which $\mathfrak M$ thinks is $\omega$). It is important to know, $\omega^\mathfrak M$ may not even be countable! In such case $\mathfrak M$ may think that things are countable even if they are not, as it compares things to its own $\omega$ (which we know is uncountable).
Since $\mathfrak M$ is small, it may know some sets which are truly countable, but it may not know about the bijections these sets have with the true $\omega$, it may be the case that $\omega^\mathfrak M$ is itself uncountable (but $\mathfrak M$ is unaware to this fact, since it judges countability wrong) and then $\mathfrak M$ will get "most" things wrong about countability.
So we end up with the following situation:


*

*There is an absolute notion of countability. This is what the universe decides, or knows, is countable.

*Every model inside the universe has its own version of $\omega$ which may be the true $\omega$, may be a different countable set, and in the worst possible case may not even be a countable set! Inside such model, $\mathfrak M$, a set $A$ is countable if the model knows about a bijection between the "local" $\omega^\mathfrak M$ and $A$.

*We can then extend such $\mathfrak M$ to a slightly larger $\mathfrak N$ in which some set $A$ which in $\mathfrak M$ was not countable, $\mathfrak N$ thinks is countable (we added the needed bijection).


We separate the case of 1, where the countability is absolute (or "true") even if internally some model $\mathfrak M$ may not know that some set is countable, from the cases of 2 and 3 in which a certain model thinks of a set as countable, or uncountable, regardless of its true size.
