How are paleomagnetic polarities determined?
This is a big question: it essentially translates to ‘how do we do palaeomagnetism’? I will try to give a brief overview and links to more detailed explanations. I'm also going to focus on the ‘how’, and leave the ‘why’ to someone else (perhaps it would be best split out into a separate question?). To record the geomagnetic field, you need three things:


A ferromagnetic mineral -- that is, one that can be magnetized like a compass needle.
A situation where grains of this mineral can have their magnetization aligned with the earth's field.
An event that locks the magnetization in place once it's aligned.


There are a surprising number of ways that (2) and (3) can happen, but for this answer I'll just describe the two that tend to be most useful: thermal remanent magnetization (TRM) and depositional remanent magnetization (DRM).

Thermal remanent magnetization is induced when a rock cools from a hot (often molten) state. Here, (2) occurs because, above a certain temperature called the blocking temperature, the magnetization of a mineral is able to change freely to align itself with the earth's magnetic field. As the rock cools, it becomes harder for the magnetization to align, and eventually it is locked in place.

Depositional remanent magnetization occurs in sediments, and is induced when grains of a magnetic mineral fall through the water column and land on the sea floor (or lake bottom). While they are in the water column, the grains are free to move and align themselves with the geomagnetic field. Once on the bottom, they gradually become buried in more layers of sediment, fixing their original orientation.

In principle, recovering the recorded field from a piece of rock is very simple: you record the rock's orientation, cut or drill it from its current situation, then measure its magnetic field in a laboratory magnetometer. In an ideal world, the field you measure would correspond to the Earth's magnetic field when the rock was formed. In practice, it's rarely that simple, and you might need to use heat treatment or alternating-field demagnetization to ‘peel off’ weaker magnetizations that have been layered on top of the original magnetization over the years.

This answer is a gross simplification and glosses over a great deal of theory, practical detail, and possible complication. For more depth, I would direct you to two excellent textbooks which (thanks to the magnanimity of their authors) are freely available online:

Tauxe, L., Banerjee, S. K., Butler, R. F. and van der Voo, R. (2014). Essentials of Paleomagnetism, third web edition. http://earthref.org/MAGIC/books/Tauxe/Essentials/ (accessed 2014-04-17)

Butler, R. F., (2004). Paleomagnetism: Magnetic Domains to Geologic Terranes. electronic edition. http://www.geo.arizona.edu/Paleomag/book/ (accessed 2014-04-17)

Tauxe et al. (2014) is more recent and more extensive; Butler (2004) is an electronic reprint of a 1992 book, but is still an excellent introductory work, and provides (to my mind) a slightly gentler introduction than Tauxe et al. (2014). (While many advances have been made since 1992, the basic theory and techniques have not changed.)

If you are interested in the nitty gritty of how the techniques are actually applied, you might want to look at:

Richter, C., Acton, G., Endris, C. and Radsted, M. (2007). Handbook for shipboard paleomagnetists. ODP Technical Note 34, Texas A&amp;M University, College Station, Texas, USA: Ocean Drilling Program. http://www-odp.tamu.edu/publications/tnotes/tn34/TNOTE_34.PDF (accessed 2014-04-17)