There are a couple of things to note about the map. First, the lines of latitude are the same distance apart, which means it is in an equirectangular projection. The upshot of this is that neither distances or angles are preserved making it not so useful for navigation. The second point is that it has a scale bar in linear units. Because distances on the ground vary according to their latitude when viewed on this map, the scale is mostly meaningless.
However, as this is a game world, you are at liberty to play around with it to your heart's content. The first thing you can do is decide how big a world it is by assuming the scalebar represents horizontal distances at the equator. It looks to be about 32 degrees over 1000km, giving you an equatorial circumference of 11,250,000m and a radius of 1790493.11m, making it about the size of the moon. The next thing is that the earth is approximately an ellipsoid, being flatter at the poles. For the earth, the inverse ratio of pole-to-pole radius and equatorial is about 298.25, the moon is almost spherical at 800.
Armed with that information, you are able to create your proj4 definition:
+proj=eqc +a=1790493.11 +lat_ts=0 +lon_0=0 +rf=800 +units=m +no_defs
+lat_ts isn't strictly necessary, but is useful for reference. It is the "latitude of true scale", which is what we based our equatorial circumference from. +lon_0 represents the longitude of the centre of the map, which in this case is the prime meridian.
Opening up QGIS and selecting Custom CRS..., I've put in our parameters into the test box, and entered north 0, east 32, which gives me 1,000,000m which is our 1,000km we were expecting for that many degrees at the equator. So go ahead and create your own CRS with a memorable name.
Now you just need to georeference the map by using the georeferencer plugin, and choosing three known points. When I did it, I put one at the equator/prime meridian, one 32 degrees (ish) east on the equator, one 32 degrees (ish) north on the prime meridian. Both these latter points have x and y values of 1000000 respectively.
And that's it! As I said before however, in this projection your east-west distances will be increasingly inaccurate away from the equator, so it might be worth creating a few more "local" projections for different countries, as well as a lat/long CRS, but that is getting a bit deep at this stage. You may find it helpful to read up on map projections (just Google it), and read the Wikipedia entry for map projections, which should give you a better idea of how it all works.
Incidentally, a long/lat CRS for your world will simply be:
+proj=lonlat +a=1790493.11 +rf=800 +no_defs
Best Answer
Not tested, but you could use a projected CRS to make your grid and then deproject the resulting shapefile to lat/lon geographic. This will distort the hexagons though.
In my part of the world (about 1-deg W, 51-deg N) 50 metres on the ground is roughly equivalent to 0.0004530 of a degree of latitude. 50 metres on the ground is also roughly equivalent to 0.0007170 of a degree of longitude. Using these values with the mmqgis plug-in it was possible to make a form of WGS84 lat/lon hexagon grid.
The attached picture shows such a grid, on a projected map image that is badly-distorted as a consequence of being reprojected on the fly to EPSG:4326.
But I would not trust such a grid as far as I could throw it. For what it's worth, my suggestion would be that if possible you change your project CRS to a projected one and use the mmqgis plug-in to make your hexagon grid using units of distance.
Nick.