I'm just starting out with woodworking, and as I don't have a project I want to complete as yet, I'm interested in making many of the tools I'd use as part of the learning process (mallets, squares, marker gauge etc).
This is how I am learning woodworking, and eventually metalworking, as well. It's a good way to go. Building squares is a nice little project.
So how can you make a square, without using a square?
You are right that there seems at first to be a chicken-and-egg problem here.
It is possible to make an accurate square without having an accurate square to check it, but you need things that are straight.
Suppose you can obtain two pieces of wood that have at least one flat, straight side. Those will be the outer sides of your square. Use one of the pieces to draw a straight horizontal line on something flat.
Temporarily join the two pieces together such that they can still be rotated with respect to each other -- like, put a single screw through them, or a single dowel, or whatever. Get them as square as you can. Then put one side along the line you just drew with the square arranged like the letter L, and use your new square to draw the perpendicular line. Now flip the whole thing over, so that it is now a backwards L, and try to draw the exact same perpendicular line. If the square is accurate, the perpendiculars will coincide. If it is not, you can estimate how far out of square your square is, adjust it, and try again.
Keep doing that until you get something that is as close to square as you want it to be, and put another fastener into the square so that it can no longer rotate, and hey, you have an accurate square built out of only an accurate straight line.
Now of course the question is "how do I produce an accurate straight line?" But that's another question.
How were they originally made if the accuracy needed to be right, but modern methods of measurement and manufacture were not available.
You do not say how far back in history you want to go. The ways that the ancient Egyptians made sure their building blocks were square are rather different than the ways that medieval carpenters used to make square buildings, and those are rather different than the techniques used to build square, accurate machine tools during the industrial revolution. Make your question more precise if you are interested in the history of tool building.
I've been watching a lot of Paul Sellers youtube videos and they have spurred me on.
woodgears.ca is also a good site for this sort of thing; there are videos there on how to make your own try squares, framing squares, and so on.