Aristocrats used the three names (praenomen, nomen, cognomen), while lesser Romans often just used the first two.
The praenomen was usually one of just a very few names (10 or so, as I recall)- and
Marcus is the only one that sounds remotely usuable today, so that's what modern authors inevitably use for sympathetic characters. First-born sons were almost invariably given their father's praenomen. A Nomen is like a surname, and the final cognomen designated a particular branch of the family (like a double-barrelled surname today) or in the rare case of a prominent politician or whatever, an honorific.
Women's names were just the feminine form of their husband or fathers' nomen, for the most part, with "maior" or "minor" or prima, secunda, tertia etc.
The common
Roman Praenomen were
Marcus,
Gaius,
Gnaeus,
Publius,
Lucius (loo-key-us in latin, not loo-shus),
Titus,
Quintus,
Sextus, Decimus...that's about it for what I remember.
This link has much information, though it's a little old (from a 1905 ish textbook- very famous!)
http://www.forumromanum.org/life/johnston_2.html#41
sa