—Morin, first Maiden of the Spear, speaking to Jeordam
Around the end of the Breaking when the surface of the world was not changing rapidly anymore and both the Tuatha'an and the Aiel separated from the Da'shain Aiel – called Jenn Aiel by that time –, the unarmed Jenn were easy prey to the rest of the world who has just turned back to barbarism. The Jenn were keeping The Way of the Leaf and their promise to the Aes Sedai, carrying their objects on their wagons, giving rather their life than abandon them. Armed people often attacked their wagons, taking gold, food, whatever they wanted to take, including killing or kidnapping women and children. When their loved ones were taken, some of the Jenn asked help from the Aiel who were following them and guarding them from a distance. The Jenn otherwise ignored the Aiel.
One day, after such attack a woman called Morin came with four other Jenn, asking for help. Her story is told in the Third vision of Rand al'Thor when he visited the glass forest ter'angreal in Rhuidean.
The Aiel helped the Jenn and offered them to stay with them by taking the spear and use it for not just self-defence but the defence of the rest as well. But after that they could never go back to the Jenn anymore.
Morin took a spear, although the leader of the sept, Lewin, told her that it is not required from women to do so. Morin wanted to participate in the rescue of her kidnapped daughter Kirin. Lewin's son, Jeordam told her that she cannot use the spear in women's dress but she has to wear men's clothes instead. Also he shortened the original length of a spear for her. When he started to work out how to use it, it is indicated that there might be a future relationship between Morin and Jeordam. (In that case, Morin is an ancestor of Rand al'Thor.)
Although she was married to a man who stayed back with the Jenn, she took the spear saying:
The shortened spear – invented by Jeordam – soon becomes the standard weaponry of all Aiel.
—Prophecy of Rhuidean
Becoming a Maiden
Almost every girl dreams of becoming a Maiden so they learn the basics of bow and spear, and fighting with hands and feet. They learn the survival techniques as well as building enormous strength of body by serious exercising. Then as a final step they "Wed the Spear". 
Marriage and pregnancy
In the Third Age, when Maiden of the Spear marry they have to leave the society, "Giving up the Spear" as they refer it. They can have love affairs without marriage, but when they get pregnant, they are forbidden to carry the spear while they carry a child. After they give birth, their child is given to the Wise Ones who find a step-mother to the child in a way that nobody can track back the identity of the real mother. The child is also raised without knowing that they were a Maiden's child. That explains why Rand al'Thor is so special, being the only child whose mother is known to be a Maiden. Also why his mother never married to his father Janduin. Janduin loved Shaiel so much he couldn't forbid her from fighting. So the prophecies got fulfilled by her giving birth to Rand after a battle at the end of the Aiel War.
Becoming a Wise One
When a Maiden is to become a Wise One (having to always do so if it is discovered that she is a channeler or Dreamwalker), she must throw away all her clothes and weapons like rubbish. If she returns from Rhuidean, she has to burn all what she can and give the metal parts to a smith who creates simple things from it. Not weapons, not even knives, but buckles or pots, or puzzles for children. She has to give these things away with her own hands. If someone never returns, all her belongings transferred to their family or relatives for remembrance.
List of Wise Ones who were Maidens
Maidens have their own "handtalk" or sign language which consists of finger spelling as well as complete words and phrases. Many societies, male and female, have their own set of handtalk, but Far Dareis Mai are the only ones that have nearly a full language in handtalk alone. It is known only to other Maidens, though Faile was taught some by Bain and Chiad and Elayne was taught some by Aviendha.
Occasionally male lovers, who cannot persuade their Maiden lover to give up the Spear, arrange for themselves to be taken as gai'shain - of course the Maiden would not look at a man in white, and the first thing she will do is teach him to sing for her sister Maidens.
Maidens accompany Rand as his honor guard. When he first comes to the Waste he tells the Maidens that they "carry his honor," a task they take very seriously. Though he has no society or sept, he was born of a Maiden and is regarded by them as "the first son of a Maiden to come back to us." They will not allow his honor to be represented by any other group, and feel gravely slighted when left behind by Rand - they cannot comprehend his reluctance to commit them to battle (because of his aversion to any harm coming to women).
The Maidens have a variety of attitudes toward Rand. Like other Aiel, the Maidens definitely do not take his commands as law; but they, more than most, readily disobey his commands that they consider "foolish." They listen to Rand's instructions in battle, but they find it unacceptable when he leaves them out of the battle - and they are willing to show their anger when he treats them as somehow less than the other male societies. At one point he is severely beaten while in his private chamber with Min. Many of the Far Dareis Mai treat him as a brother or a son - irrespective of their relative age. Maidens twice his age may joke with him like a brother, and Maidens younger than him may just as easily pester after him to make sure he's not too cold at night.