How can scientists know where the earliest continents were located? Supposedly, Pangaea has formed, re-formed, moved all around, etc.
Do paleogeologists primarily rely on paleomagnetism, paleontology, or what?
Well, the really earliest continents, the answer is we don't. As you go further back the uncertainties get larger and larger. It has been speculated that there have been around 4-5 super continents like Pangaea. Before Pangaea there was Rodinia, but before that it gets more and more sketchy.
The oldest ocean floor is only Jurassic. So ocean palaeomagnetism is only good back to the Jurassic, but can be extrapolated a bit beyond that. You have continental magnetism and this helps place the palaeo-latitude - for example, we know the UK was just south of the Equator in the early Palaeozoic. That doesn't give you relative location but is an important piece of the jigsaw.
The other is stratigraphy. Yes that includes palaeontology, but before the Palaeozoic, palaeontology is limited (eg. do Ediacaran species have global or regional distribution? what about earlier single celled organisms?). It can also include rock correlations, isotope signatures, etc. For example, the Lewisian Gneiss is a piece of Archaeon craton in NW Scotland that has some well studied dyke sequences. If you find similar gneisses elsewhere with the same dates and dykes with the same chemical signatures, then you can hypothesise they were a part of the same unit and they split after the dyke intrusion.