Define a partial order on natural-valued functions (or sequences, depends on how you see it): $f<g$ iff $\exists x:\forall n(n>x\rightarrow f(n)<g(n))$.
Intuitively, $f<g$ if $g$ increases more than $f$.
Now, a set $A$ of functions is cofinal if it contains arbitrarily 'large' functions- $\forall f$ , $\exists g\in A:f<g$.
My question is, how big do these cofinal sets have to be?
$A$ clearly can't be finite; If it has a maximal element $g$, then the function $h$ defined by $h(x)=g(x)+1$ is bigger than $g$. However, I don't know whether $A$ can be countable or not. If it can, is there a way to construct such an $A$, or does it rely on nonconstructive tools (Axiom of Choice)?
What happens when we generalize the question, for say real-valued sequences $\{f:\mathbb{N}\rightarrow \mathbb{R}\}$ or even real-valued functions?
Great question! This is connected with what are known as cardinal characteristics of the continuum; specifically, you're asking about the dominating number, $\mathfrak{d}$ - the least size of any dominating family (in your terms, "cofinal family"). See also https://mathoverflow.net/questions/29624/how-many-orders-of-infinity-are-there.
We can in fact show that $\mathfrak{d}$ is uncountable, as follows. Fix any countable set $\{f_i: i\in\mathbb{N}\}$ of functions on $\mathbb{N}$. Now let $g$ be defined as $$g(n)=1+\sum_{i<n}f_i(n).$$ It's easy to see that $g$ dominates every $f_i$.
Conversely, we clearly have $\mathfrak{d}\le 2^{\aleph_0}$. In the presence of the continuumy hypothesis "$\aleph_1=2^{\aleph_0}$," this of course determines $\mathfrak{d}=2^{\aleph_0}$; however, we can ask what happens in the absence of the continuum hypothesis.
The answer, perhaps surprisingly, is: practically anything! It is consistent with ZFC, for instance, that $\mathfrak{d}=\aleph_1<2^{\aleph_0}$.
Things get much more interesting if we ask how $\mathfrak{d}$ can interact with other cardinal characteristics of the continuum, such as:
The smallest $\kappa$ such that the union of $\kappa$-many measure-zero sets is not measure zero.
The smallest $\kappa$ such that there is a family of $\kappa$-many functions not dominated by any single function (the "dual" of $\mathfrak{d}$, the bounding number $\mathfrak{b}$).
The smallest cardinality of a maximal almost disjoint family - a family of infinite subsets of $\mathbb{N}$ which have finite pairwise intersections, and is maximal with this property.
Etc.
When we ask about comparing pairs of cardinal characteristics of the continuum, this is very well-understood; see Cichon's Diagram https://en.wikipedia.org/wiki/Cicho%C5%84%27s_diagram. For instance, even though they sound very similar, ZFC proves $\mathfrak{b}\le\mathfrak{d}$, and it is consistent with ZFC that $\mathfrak{b}<\mathfrak{d}$, so there is an asymmetry there.
When we ask about three or more cardinal characteristics at once, this gets very hard, and until relatively recently very little was known; see https://mathoverflow.net/questions/37188/consistency-results-separating-three-cardinal-characteristics-simultaneously.
EDIT: You also asked about finding dominating sets. Well, we can certainly just take the set of all functions $\mathbb{N}\rightarrow\mathbb{N}$, so this doesn't take any real axiomatic power. But what about families of minimal cardinality? Well, here things get interesting; for one thing, without the axiom of choice there might not be any dominating families of minimal cardinality ($\mathfrak{d}$ could be undefined)! See https://mathoverflow.net/questions/191545/cardinal-characteristics-without-choice. And even with AC, we can show that if $\mathfrak{d}<2^{\aleph_0}$ then any minimal-cardinality dominating family is really hard to define (e.g., non-Borel, and - assuming large cardinals - non-projective as well) simply because so is every set of cardinality between $\aleph_0$ and $2^{\aleph_0}$.
So there doesn't seem to be a really solid answer to "How hard is it to find nontrivial dominating families?", but certainly "Pretty hard" is a good start.
As to generalizations:
Certainly the dominating number for $\mathbb{N}\rightarrow\mathbb{R}$ is just $\mathfrak{d}$ again. Given $f: \mathbb{N}\rightarrow\mathbb{R}$, let $f':\mathbb{N}\rightarrow\mathbb{N}: n\mapsto\lceil f(n)\rceil$. Then
Any dominating family $\{f_i: i\in I\}$ of maps $\mathbb{N}\rightarrow\mathbb{N}$ is also a dominating family $\{f_i: i\in I\}$ of maps $\mathbb{N}\rightarrow\mathbb{R}$.
Meanwhile, if $\{g_i: i\in I\}$ is a dominating family of maps $\mathbb{N}\rightarrow\mathbb{R}$, then $\{g_i': i\in I\}$ is a dominating family of maps $\mathbb{N}\rightarrow \mathbb{N}$.
However, if we look at maps $\mathbb{R}\rightarrow\mathbb{R}$, things get much messier. First of all, we need to refine our notion of domination of functions: by "$f<g$" do we mean $$f(x)<g(x)\mbox{ for all but finitely many $x$}$$ or $$f(x)<g(x)\mbox{ for all but boundedly-many $x$}$$ or $$f(x)<g(x)\mbox{ for all but bounded-from-above many $x$}$$ or something else?
To just play around for a moment, let's look at the first case: $f<g$ if $f(x)<g(x)$ for all but finitely many $x$. In this case, any dominating family must have size $>2^{\aleph_0}$ (so the number does change, quite a lot). To see why, let $\{f_i: i< 2^{\aleph_0}\}$ be any family of continuum-many maps from $\mathbb{R}$ to $\mathbb{R}$. Now build $g$ such that $g(x)>f_i(x)$ for infinitely many $i$, as follows: write $\mathbb{R}$ as a partition of continuum-many infinite sets $A_i$, and let $g(x)=f_i(x)+1$ for each $x\in A_i$. Certainly $g$ doesn't dominate $f_i$ - this is a difference from the argument that the original dominating number is uncountable! - but also clearly $f_i$ doesn't dominate $g$.
We can use similar arguments on every other notion of domination I can think of. However, the relationships of the exact values of the generalized bounding numbers is not clear to me. For instance;
Note the switch from "$<$" to "$\le$", which I think is more natural for a variety of reasons.
Such "higher" cardinal characteristics have been studied a little, although (as far as I can tell) not extensively; see e.g. http://www.sciencedirect.com/science/article/pii/016800729500003Y.