How were the designations of "North" and "South" applied to the hemispheres of Mars? How was it decided which hemisphere was North and which hemisphere was South on Mars? Clearly, the designations "North" and "South" apply only to the hemispheres which contain the axis of rotation at their center, but what determined whether a hemisphere received "North" or "South" as its designation?
The research in other answers helped me come across the actual International Astronomical Union (IAU) standard:


  The north pole is that pole of rotation that lies on the north side of the invariable plane of the solar system.


The north of the invariable plane is the side that Earth's North pole points to. In fact, one of our other users has observed:


  The North Pole of any system being the pole on the same side as earth's north is indeed the correct definition. This applies to the Milky Way galaxy as well, in which case the North Galactic Pole is the pole towards the hemisphere of the galactic sphere which also contains the celestial north pole.


Dwarf planets, minor planets, their satellites, and comets do follow the right-hand rule mentioned in other answers (see Axial tilt on Wikipedia).

Sources:


Report of the IAU/IAG Working Group on cartographic
coordinates and rotational elements: 2006 - P. Kenneth Seidelmann, B. A. Archinal,
M. F. A’hearn, et al.
Poles of astronomical bodies - Wikipedia