The praenomen was the personal name, and there were very few to choose from: Caius or Gaius (the most common), Cnaeus or Gnaeus, Titus, Tiberius, Quintus, Aulus, Decimus, Lucius, Marcus, Postumus, Publius, Quadratus, Sextus, Servius, Spurius, and maybe Primus and Tertius.   That's about it.  Nova Roma also lists Flavius and Cassius, but those are nomina and were certainly not praenomina until the 3rd or 4th century.

       The nomen is the name of the family or gens, and almost always ends in -ius.  Julius, Flavius, Claudius, Didius, etc.  Using a well-known nomen like Julius is fine because there were non-noble branches of famous families, and freed slaves took the names of their former owners.  (See list below.)

       The cognomen can indicate the branch of the family, or be another given name, or be a nickname like Celer or Felix, or the town or tribal name of a provincial.  The cognomen was not universal until about the first century BC, hence Gaius Marius.  (See list below.)

       Gaius Julius Caesar was the son of Gaius Julius Caesar, but his uncle was Sextus Julius Caesar.  Upon his death he adopted Gaius Octavius Thurinus, who took the name Gaius Julius Caesar Octavianus.  The emperor Vespasian was Titus Flavius Vespasianus and his brother was Titus Flavius Sabinus; his sons now known as Titus and Domitian were Titus Flavius Vespasianus and Titus Flavius Domitianus (named after his mother Domitia).  One of them was ruling when a young Thracian named Bassa joined a Roman auxiliary unit and took the name Titus Flavius Bassus.

       Girls were simply given their father's nomen, feminized, and sometimes a cognomen or a nickname such as a diminutive of her father's nomen or cognomen.  Therefore, all of Julius Caesar's daughters and sisters were named Julia, though may have been called Julilla, etc.  Apparently some girls were simply numbered: Prima, Secunda, Tertia, etc. (My wife is Hortensia Tertia because she likes gardening and has 2 older sisters.)  Women did not change their names when they married.  The Nova Roma list of women's names includes a number of feminized men's nomina.
       Just how formally the rules were followed in the lower classes is hard to say, but there are very few names known from inscriptions, etc., that don't make logical sense.  Actually, in the most formal usage, as on tombstones, a man's name had 6 parts: praenomen, nomen, filiation ("son of..."), cognomen, origo (place born), and voting tribe.  Not that that would help greatly--it could still all be identical to your father's name!

NOMINA (This is not a complete list):

Abudius Adaucius Aelius Aemilius Aeresius Afranius Albius Ammonius Antonius Apuleius Arrenius Anicius Antonius Artorius Audacilius Aufidius Aurelius Babudius Caecilius Caelius Caesennius Caesidius Calidius Calpurnius Cammidius Cammius Camurius Carausius Cassius

Celerinius Censorius Claudius Clodius Cornelius Curtius Decrius Desticius Didius Domitius Duccius Ecimius Eprius Exomnius Fabius Fannius Favonius Flavius Gargilius Grattius Helvidius Helvius Honorius Hortensius Hosidius Ingenuius Julius Juventius Larcius

Latinius Liburnius Licinius Ligustinius Livius Lollius Lousius Lucretius Maenius Manlius Mannius Marius Menius Mercatius Messorius Minicius Mommius Mummius Mucius Munatius Mussius Mustius Nectovelius Nemonius Neratius Nestorius Octavius Olcinius

Oppius Ostorius Paternius Peltrasius Petillius Petronius Plautius Platorius Poenius Pompeius Pomponius Pontius Porcius Postumius Praesentius Pupius Quinctilius Roscius Rustius Rutilius Saturius Sallustius Saufeius Scribonius Sempronius Septimius Sertorius Simplicius

Sittius Socellius Spurius Statilius Statorius Suetonius Sulpicius Tabellius Tadius Terentius Tertinius Thoranius Titius Trebellius Tuccius Ulpius Valerius Varius Velius Veranius Vesnius Vettius Vibius Virius Vitellius Volteius Volusius

COGNOMINA (Definitely not a complete list!):

Aelianus Agricola Agrippa Albanus Albinus Aprilis Arcanus Avitus Balbus Bassus Bellicianus Betto Caelianus Capito Castus Cattianus Celer Cerialis Civilis Clemens Coranus Corvinus Crescens Crispus Dexter Dida Disertus

Donatus Drusus Erasinus Facilis Faustus Felicissimus Felix Festus Fidus Firmus Flavinus Fortunatus Frontinus Fronto Fuscus Gaianus Galba Gallienus Gallus Gemellus Genialis Geta Gracchus Homullus Honoratus Ingenuus Justus

Libo Longinus Lucullus Lupus Macer Macrinus Macro Magnus Mansuetus Marcellus Maritimus Martialis Martius Masala Masavo Maternus Maurus Maximus Melito Messalinus Mettellus Modianus Montanus Natalis Nepos Nerva Noricus

Novanus Paetus Panthera Paulinus Pertinax Petra Picens Pius Probus Proclus Pudens Pulcher Quadratus Quietus Romanus Rufinus Rufus Rusticus Sabinus Saenus Saturninus Savius Scapula Scipio Secundus Seianus Senecio

Severus Silanus Silvanus SolonSolus Speratus Strabo Suavis Super Surinus Thurinus Valens Venator Verus Viator Victor Vindex Virilis Vitalis

WOMEN'S NAMES--Many of the following are from the index of Women's Life in Greece and Rome by Lefkowitz and Fant.  Some are recognizably Roman, some are Greek or from some other foreign culture (belonging to non-Romans or slaves), and some are mixtures.
 

Abudia Megiste Allia Potestas Antiochis Antonia Thallusa Appulia Aristarete Arria Artemis Athenodora Atia Aurelia Leite Aurelia Philmatio Bassilla Caprasia Cassia Secunda Claudia Clodia Cornelia Didymarion Didyme Dionysia Domnina Drusilla Epicydilla Epidia Epria

Eucharis Extricata Fannia Flavia Publia Nimachis Flavia Sabina Gaia Afrania Gnome Hedea Helvia Hilara Hortensia Irene Isidora Italia Julia Domna Julia Livilla Julia Pye Junia Theodora Lalla Larcia Horaea Licinia Magnilla Melino Melitine Messalina Minicia Marcella

Minucia Asste Modia Quintia Murdia Musa Mussia Dionysia Nitocris Olympias Olympionica Paezusa Panthia Parthenia Perenice Phamphile Phyllis Pobicia Aphe Politta Posilla Senenia Primilla Quarta Senenia Recepta Sallustia Athenais Saufeia Thalea Scholastica Semiramis Socratea Statilla

Statillia Tyrannis Sulpicia Telephoris Terentia Prima Tertia Aemilia Thuria Timarete Tryphosa Urbana Venuleia Sosis

a = as in "ah"
ae = "eye"
c = always hard like K
g = always hard as in "girl"
i = short as in "pit", or long as in "pizza".  When used as a consonant, = Y
j = not used in proper Latin--represents consonantal i and pronounced as Y
u = as in "doom" when a vowel, or as W when consonant.  Properly written v.
v = u

Gaius = GUY-oos
Caesar = KAI-sar
provincia = pro-WINK-ee-ah
Vesuvius = wes-OO-wee-us
Adlocvtio = odd-low-COO-tee-oh
gladius = GLAH-dee-oos
pugio = POO-gee-oh (not POO-jee-oh!)
pilum = PEE-loom
caligae = CAH-lee-guy (not Caligula!)

Ave = AH-way--Means "Hail", Hello or Greetings
Salve = SAHL-way--also Greetings
Vale = WAH-lay--Farewell, goodbye
   --The plurals of these, used when addressing more than one person, are Avete, Salvete, and Valete.