How many countable graphs are there?

Here is one explicit way of producing continuum-many pairwise nonisomorphic (simple, undirected, loopless) graphs.

Start with a $3$-cycle among vertices labelled $-2,-1,0$. To the vertex $-1$ attach a tail (= path) of length $1$ and to the vertex $-2$ attach a tail of length $2$. Now, for each positive integer $n$, attach a tail of length $n$ to the vertex $0$, and label the terminal vertex in this tail $n$. (So we have some vertices that we have not labelled, but certainly only countably many of them.)

Now focus on the vertices marked $1,2,3,\ldots$: color the odd numbered ones red and the even numbered ones green. Consider the set of all possible bipartite graphs on this vertex set -- i.e., in which all edges connect red to green. There are clearly continuum-many: for instance even the independent choices of including / not including the edges $1--2$, $1--4$, $1--6$, and so forth gives a set of continuum cardinality. I claim that all of these graphs are pairwise nonisomorphic. Indeed, the only three cycle in any of them is formed by the vertices $-2,-1,0$, and it follows easily from this that any isomorphism between any two of these graphs carries $0$ to $0$, $-1$ to $-1$ and $-2$ to $-2$. From this it follows that for all $n \in \mathbb{Z}^+$, an isomorphism takes the vertex labelled $n$ to the vertex labelled $n$ and thus every vertex is fixed.

(By the way, I don't find the argument you suggest to be at all valid. I strongly suspect there are first order theories such that the number of nonisomorphic models of finite size $n$ grows at least exponentially with $n$ but for which there are only countably many isomorphism classes of countable models.)

Added: I want to make sure that the paths from $0$ to $n$ stay pairwise nonisomorphic when edges are added, so it's best to modify the construction slightly. For instance, call the penultimate vertex in the path $p_n$ and attach one more length one tail at $p_n$, so that now $p_n$ has degree $3$.

One way is to construct an injection from $2^{\mathbb{N}}$ (or from some other uncountable set) to the set of countable graphs. There are many, many ways to do this.

Here's one way: I will construct a countable graph corresponding to a function $f: \mathbb{N} \rightarrow \{0,1\}$. The graph has vertices $y$ and $x_{n,i}$ for $n \in \mathbb{N}$ and $1 \leq i \leq n+1$. For each fixed $n$, we connect $x_{n,i}$ for all $i$ (in a chain as Alex suggests, or a loop, or a complete graph-- any will work). Then we add an edge from $y$ to $x_{n,1}$ if $f(n)=1$.

This is indeed an injection; we can recover $f$.

Edit: At first I had a multigraph construction, with multiple edges to each vertex, which is not what the question wanted. I have modified the construction to make a simple graph.

Here is a bijection between $[0,1) \subset \mathbb{R}$, which is uncountable, and a pairwise non-isomorphic collection of countably infinite graphs:

For $x \in [0,1)$, let $0.x_1 x_2 x_3 ....$ be its unique decimal expansion (so $0\le x_i<10$ for each $i$, and no expansion ends in infinitely many 9's). Construct the graph $G_x$ as follows: start with the 3-cycle on $\{a,b,c\}$; attach the infinite chain $(a,1,2,3,...)$ to node $a$; and attach a chain of length $x_i$ to each node $i \ge 1$.

A minimal modification of this (use chain length $x_1 x_2 ... x_i$ in place of $x_i$) gives a bijection that preserves the order relation: $G_x$ is a subgraph of $G_y$ if and only if $x \le y$.