The construction is two circles. Take a segment AB. With centre A and radius AB draw a circle; with centre B and the same radius draw another. Each circle passes through the other's centre. The lens-shaped region where the two overlap is the vesica piscis.
This is not a decorative figure grafted onto geometry afterwards. It is Proposition 1 of Book I of the Elements, the first thing Euclid shows how to do. His purpose is not the lens but the two points where the circles cross: joining either crossing point to A and to B gives three segments all equal to the radius, and therefore an equilateral triangle on AB. The vesica is what the equilateral triangle is built out of.
Almost every elementary construction starts here. The two crossing points define a line, and that line is the perpendicular bisector of AB, which delivers the midpoint of a segment and a right angle in a single move. Apply the same trick from a point to a line and you have a perpendicular through it. Strike arcs about the arms of an angle and repeat, and you have the angle bisector. The vesica is the workhorse of compass work, and anyone who has done school constructions has drawn hundreds of them without being told the shape had a name.
The name itself is Latin for fish bladder and describes the outline. In Italian art history the same shape framing a figure is called a mandorla, almond. German medieval architectural vocabulary calls the related tracery form a Fischblase, fish bladder again. The names are late. The construction is as old as Greek geometry and older in practice, since striking two arcs to find a midpoint is what anybody laying out a building does.