Is there a minimum number of vertices that a graph must have to be of a given genus? It seems intuitive that the higher the genus of a graph the more vertices and edges it would have to have.  Is it known if the minimum number of vertices must be larger for graphs of higher genus?

There is at least an upper bound on the genus in terms of the number of vertices and edges in the graph. Let $\gamma(G)$ be the genus of a graph $G=(V,E)$ and $\beta(G)=|E|-|V|+1$ be its Betti number. Then the following holds:
$$\gamma(G)\leq\left\lceil\frac{\beta(G)}{2}\right\rceil$$
For a reference on how to prove this see for example this paper
