**Edited 27 September 2016**

(An earlier version of this answer incorrectly claimed to show that the genus of the McGee graph was 3. **In fact, the genus of the McGee graph is 2.** Thanks to Gordon Royle, who pointed out this mistake.)

The image above shows how to embed the McGee graph into a surface of genus 2. There are 10 oriented cycles here (8 of length 7, and 2 of length 8) which contain each edge twice with opposite orientations. So the Euler characteristic of the oriented surface in which the graph is embedded here is $\chi=24-36+10=-2$, and its genus is $g=2$.

We can prove that this is the minimum genus as follows:

Suppose we've embedded the graph in an orientable surface, so that the surface is decomposed into $F$ regions. These regions might not all be simply connected, so in general we will say that each has $b_i$ connected components to its boundary, and the $j$th connected component of the boundary of the $i$th region is comprised of $n_{i,j}$ edges of the graph, forming a cycle of the graph.

Since each of the 36 edges of the graph appears twice in these boundaries, we have:

$$\sum_{i=1}^F \sum_{j=1}^{b_i} n_{i,j} = 2 \times 36 = 72$$

But the smallest cycles in the graph have length 7, so:

$$7 \sum_{i=1}^F b_i \le 72$$

Since the $b_i$ are integers, it follows that:

$$\sum_{i=1}^F b_i \le 10$$

If the total number of holes in all the regions is $H$, we have:

$$F + H = \sum_{i=1}^F b_i \le 10$$

A division of the surface into $F$ regions with a total of $H$ holes can be converted into a division into $F$ *simply connected* regions by adding $H$ additional edges, without changing the number of vertices (e.g. an annulus can be converted into a disk by adding one edge). Counting these $H$ supplementary edges in addition to the $E$ edges of the graph, we have the Euler characteristic for an orientable surface of genus $g$:

$$V - (E+H) + F = 24 - 36 + F - H = 2 - 2g$$
$$g = 7 - \frac{1}{2}(F-H)$$

But we have:

$$F-H = F+H-2H \le 10-2H$$
$$g \ge 2+H$$

So the genus of the surface must be at least 2, and $g=2$ is only possible when $H=0$ and the surface is divided into $F=10$ simply connected regions.

There is also a nice, symmetrical embedding of this graph into a surface of genus 3:

The image above shows 8 oriented 9-gons, arranged so that pairs of oppositely-oriented edges from different 9-gons form the edges of the McGee graph. So the Euler characteristic of the oriented surface in which the graph is embedded here is $\chi=24-36+8=-4$, and its genus is $g=3$.

Any dihedral symmetry of the original planar embedding of the graph just permutes these eight 9-gons among themselves. The other graph automorphisms give different 9-gons on the planar embedding, for example:

The Riemann surface for the genus 3 embedding looks like this:

where edges and faces with the same numbers should be identified. The complete symmetry group of this surface is the 16-element dihedral group, with the orientation-preserving symmetries giving an 8-element cyclic subgroup.