Names for women were easier, so we'll go there first. Although there is inscriptional evidence that women originally had their own first names, they lost them in the early republic. Thereafter, all female children of citizen families were named with the feminine form of the name of the clan or gens into which they were born; hence, all women whose fathers were in the Julius clan were named Julia, and all women whose fathers were of the Cornelius clan were named Cornelia, etc. In public, women would be identified by the possessive form of their father's name (e.g., Julia Caesaris, "Julia of Caesar"). If families had more than one daughter, they were first called major and minor ("elder" and "younger") and when a third daughter was born they became, for example, Julia or Cornelia Prima, Secunda, Tertia, etc. Married women used their husbands' gens name the same way: a Julia who married a man named Cornelius became a Cornelia.
Male Roman naming conventions were more complex than those for women. The three basic male names were the praenomen or first name, the nomen or clan (gens) name, and the cognomen or nickname. There were only about thirty authentic Roman praenomina and only about ten were in common use. Any particular clan would only use three or four praenomina, and some uncommon names were only used by one tribe -- if your first name was Sextus, for example, you were either a member of the Julii gens or an interloper who has picked an obviously false name. In written form, first names were almost always abbreviated by one or two letters. Some abbreviations reflected archaic spellings of praenomina, for example, C. for Gaius and Cn. for Gnaius.
There were almost 300 recognized clan or gens names, and the always ended with the letters "-ius" (as in "Julius" or "Claudius"). Most, if not all, of these clan nomina are thought to have been derived from archaic praenomina or first names (Julius from Julus, Claudius from Claudus, etc.), and the nomina continued to exist long after the respective praenomina fell into disuse. With only 300 clan names and thirty or so first names (most of the latter uncommon), the total of all acceptable combinations of first and clan names was only a few thousand. It soon became necessary to somehow distinguish among members of the same clan that had the same first name: there might be dozens of men named Caius Julius. One way used in written form was to add "filiation", the abbreviation of the father's name and the letter "f". For example, M. f." added to a written name would mean son (filius) of Marcus. Much more common was the addition of the a cognomen or nickname, the third part of the tria nomina.
And there seemed to have been an unlimited supply of nicknames, many of which were simply descriptive adjectives like Verus (truthful), Rusticus (rustic), Moderatus (moderate), Augustus (dignified), etc., which said something about an individual's personality or some distinguishing characteristic. Cognomina could also reflect a personal accomplishment (Africanus as applied to Scipio Africanus after he defeated Hannibal in North Africa). A cognomen that was particularly honorific might be passed down to future generations and achieve the status of Agnomen, which distinguished a whole family within a clan. Africanus, in fact, was one of these Agnomina, and all of Scipio Africanus' descendents proudly added Africanus behind their personal nicknames.
Many nicknames were clever or ironic. The most famous of the latter is Scaevolus (lefty) which became an agnomen for all the descendents of a soldier who burned off his own right hand to prove to an attacking enemy General how tough Romans were -- the General withdrew his forces, and Rome was saved. The famous Roman poet Publius Vergilius Maro had another "Vergilius" (meaning a fast-growing seedling) added to his name (he was then Publius Vergilius Maro Vergilius) either because of his reputed sexual prowess or lack of it -- "experts" still argue that point.
And some nicknames, although they might be accurate, were downright mean, and descendents quickly tried to forget them. Stupidus, Torpidus, and Flatulus, and even Culus (Stupid, Sleepy, Farty, and Rectum) and other highly unflattering cognomina weren't uncommon. The republican comedic playwright, Plautus, named one of his popular farces Pseudolus (false one or schemer -- the name of the title character, a slave), and, thereafter, any number of politicians and lawyers had that doubly insulting cognomen flung at them by their enemies. Finally, we can only try to guess what Caius Julius Caesar Strabo did to get the cognomen Sesquiculus, which meant "Rectum-and-a-half".
For more on Roman names -- adopted sons, freedmen, barbarians, slaves, and folk who just couldn't afford a tria nomina of their own -- visit the about.com Roman Names page at http://ancienthistory.about.com/homework/ancienthistory/cs/romannames1/index.htm.
You can pick your own Roman name (following, of course, all the proper naming conventions) to help to reestablish the Roman Republic. The NovaRoma web site at http://www.novaroma.org/via_romana/names.html gives lists of praenomina, nomina, and cognomina along with the rules of name formation.
Coins are sometimes too small to contain whole names. To see how names appeared of folks important enough to be on coins, go to http://www.bitsofhistory.com/info/r_names.html.
Some Modern names have Roman/Latin origins. Are you on the list? http://www.geocities.com/Athens/Forum/6946/names.html