The only time this really came up in Britain (I'm not going to pretend to know much about anywhere else, and I'm only thinking of the centuries after 1066 really) was in the twelfth century. It's pretty complicated, and there are disagreements among historians as to the extent to which gender came into play. This therefore is somewhat simplified (though I can supply sources if you wish).

In 1135, Henry I died. His popular and competent son William Adelin had drowned in the White Ship disaster in 1120 and Henry I had no more heirs. His daughter Matilda was abroad, but after her husband (Holy Roman Emperor Henry V) died, Henry I of England summoned her home and married her to Geoffrey of Anjou and made her his heir. His lords swore oaths to her.

It gets complicated here. Under Henry I, England and Normandy were pretty intertwined, and although Geoffrey of Anjou was useful for Henry I's borders, he was also deeply unpopular, particularly in Normandy. Additionally, as your question pointed out, Matilda was a woman. Now, it isn't clear that inheritance worked out precisely as we understand it now. For example, William the Conqeror had left his eldest son Normandy and his second son England. This makes sense in terms of giving his eldest son his ancestral duchy and his second son the lands he'd acquired- but England provided the title, was richer, and why split up the lands in any case?

So when Matilda's cousin, Stephen of Blois, seized the throne in 1135, it seemed that that would be that. He was a grandson of the conqueror (I believe he and his brother were the only two male grandchildren, and his brother had joined the church). This isn't necessarily to do with gender. It seems likely that had Matilda seized the throne, she might have kept it, but that Stephen's quick action and her unpopular husband stumped that plan.

Stephen was fine for a bit, but began pissing people off by arresting them arbitrarily and not defending his Norman territories sufficiently from Geoffrey, and a civil war (the 'anarchy') reigned until 1154, when through settlement, Matilda's son Henry II took the throne.

Clearly Matilda's gender was not enough to prevent her from having enough support to wage war for over a decade, and her father had nominated her heir. Obviously it didn't work out for her, but it's difficult to argue that this is entirely (or even at all) to do with her gender. To answer your question, Millie probably would become the next monarch, but in England at least, succession was so unstable that she'd have likely faced challengers, man or woman. Additionally, an unpopular husband, or a husband who might create a powerful faction, or just the possibility of this, would make the prospect of rule seem an even more unstable prospect than usual, because of the power that any husband of her's would gain. Mostly, the most competent and fast moving candidate got the throne, and had to work very hard to keep it. For many reasons, this was rarely a woman.

It depends on the country. Different countries had different legal systems, but an important point is that, until the late Middle Ages, a lot of the time these laws just weren't very clear. They could often be little more than tradition. And then of course, there was frequently the case that "Might makes Right". Perroybartlett has already talked about Matilda. Was she the heir? Was she not? It wasn't completely clear, so it ended up being decided by war. At the tail end of the Middle Ages, laws began to be much more solid. Henry VIII designated his heirs as follows: Edward (youngest, but a boy), Mary (oldest daughter), Elizabeth (older than Edward, but a girl, younger than Mary). As it happens, none of them had children, so they ruled in this order. So from then on, the principle was well-established that sons inherited, followed by daughters, followed by uncles, etc. Some other countries used a similar but not identical system, such as the Spanish states (and this is how Spain was united: Isabella inherited one state, Ferdinand another, they got married and their children ruled the whole thing). On the other hand, in Germany, the Salic Law system did not allow women to inherit the throne at all. To take a much later example of how this worked: King William of Britain and Hanover died. His middle brother's grandaughter (Victoria) was next in line for the throne of Britain. However, she couldn't inherit his other Crown, because that used a different succession law system where girls could not inherit, so it went to his youngest brother instead.

Finally, I'd also mention that, in the early Middle Ages, laws were not even so set as to guarentee that if Millie were a boy she'd inherit. If the prince was too young, and his uncle popular, quite likely Uncle Jack would take the throne. Or perhaps they'd split it (splitting between sons is how the Carolingian Empire ended, and why Wales was rarely united). Or perhaps they'd rule together.

For example, while Æthelwulf, King of Wessex, was on pilgrimage, his son Æthelbald tried to depose him. To avoid civil war, they split the kingdom in half, until it was reunited with Æthelwulf's death. After Æthelbald died, the throne went to his brother Æthelberht, and after that to his brother Æthelred. For example, in 871 King Æthelred died in battle against the Great Heathen Army. He left two under-age sons. But the highest Bishop had given Æthelred's younger brother (the last of the 4) Alfred, the title of Secundarias (meaning heir), confirmed by the Witan (a kind of parliament) and Æthelred and Alfred had agreed that whichever of them died first, all their political titles would be inherited by the other, not their sons. With a giant army invading, you can see why the Anglo-Saxons would much rather have an experienced warrior inherit than a child. So it wasn't always the case the sons inherited either.

The Middle Ages is a long time, with many different countries and legal systems. We tend, in the English-speaking world, to assume that it worked the way it worked in Norman England (oldest son), but it's not quite so simple. And that's before we get to places like the Eastern Roman (Byzantine) Empire, where they might have two Emperors at the same time! Or the Holy Roman Empire, where the Emperor was elected (by between 5-9 voters).

Hi OP, succession traditions can vary widely across cultures and time. Can you specify which country/culture/region and time period you're asking about - Britain in the Middle Ages for example? Thanks!