Briefly: the most honest answer is, "we mostly don't know".

Detailed records of choreography largely started in 15th century Italy -- Domenico da Piacenza is the first author from whom we have reasonably detailed MSS describing dances. So we have a fair amount of information about later Renaissance Dance from various countries (Italy, France, England, bits from Spain and Germany, from various periods over the next couple of centuries), but nothing very concrete before then.

We do have a good deal of medieval music, some of which is generally understood to be dance music (see for example Timothy McGee's Medieval Instrumental Dances, Indiana Univ. Press 2014), and a fair amount of iconography of people clearly dancing. We can draw some reasonable inferences from that (for example, many of the paintings appear to likely be simple line or round folk dances), but in general we're mostly left with guesswork, with few details.