How many countable graphs are there? Even though there are uncountably many subsets of $\mathbb{N}$ there are only countably many isomorphism classes of countably infinite - or countable, for short - models of the empty theory (with no axioms) over one unary relation.

How many isomorphism classes of
  countable models of the empty theory
  over one binary relation (a.k.a.
  graph theory) are there? I.e.: How many countable unlabeled graphs are there?

A handwaving argument might be: Since the number of unlabeled graphs with $n$ nodes grows (faster than) exponentially (as opposed to growing linearly in the case of a unary relation), there must be uncountably many countable unlabeled graphs. (Analogously to the case of subsets: the number of subsets of finite sets grows exponentially, thus (?) there are uncountably many subsets of a countably infinite set.) 
How is this argument to be made rigorous?

I assume you mean by countable graph one that is countably infinite. I will also assume that your relation can be an arbitrary binary relation and not just symmetric since you seem to be interested in that case.
In this case there are uncountably many. For, a special case of a binary relation is a total order. We do not need to add anything to the theory to have a total order; it's just a special case and ordering will be preserved by isomorphism. There are uncountably many nonisomorphic orders on a totally ordered set.
Indeed let $N$ be the natural numbers. Let $S$ be a subset of $N$. Replace each $s\in S$ by a copy of $\mathbb{Q}\cap [0,1]$ where $\mathbb{Q}$ are the rationals. It's easy to show that if $S\not = T$ then you will get nonisomorphic orders this way. But there are uncountably many subsets of $N$.
So there are uncountably many orders on a countable set.
