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).
North and south are defined according to the planet's rotation about its axis. A "right hand" rule is used: If you make a fist with your right hand, and orient your curled fingers in the direction the planet rotates, your thumb points north. Alternatively: Standing on the equator, facing the direction the planet rotates, North is to your left.
Axial Tilt on wikipedia has this information (and more.)
hey! Don't up vote this answer; It's wrong... see the comments where the OP has actually researched and discovered the real answer. (I don't want to delete this answer because we'll lose the comments too!)