You write a novel. Naturally it has characters. And those characters need names! Let us set aside for some other day the issue of creating fantasy names, and consider today only naming characters with cognomens that already exist.
Depending upon how you roll, this usually comes very early in the writing process. For me it comes before beginning the writing at all; if I don’t know the character’s name I cannot write. I can get away without looking at my hero for many thousands of words. I was more than halfway through the first draft of How Like A God before I thought to actually cast the authorial gaze upon my hero; I knew what all the other characters looked like because I was using his viewpoint, but he had never done the old look-in-a-mirror stunt. (When I did look I was astonished, and marked the place in the text.)
But there are a number of factors to consider. The most important of course is time and place. A work that takes place on Mars in AD 2502 is going to have a differently-named cast than a work that is set Splash and is around 30 years old today. You therefore are foolish indeed to name your Elizabethan heroine Brenda or Madison, and if the novel is set in ancient Rome, all I can say is for god’s sake don’t! Rome, like many other non-Western cultures, had its own naming conventions which you should research carefully.
Surnames, if your characters need them, are also a challenge. An old writer trick if you need foreign names is to look up categories of people — sports figures, say, or members of the state legislature, or plumbers. You need a Czech villain? Find the list of the members of the Czechoslovak Olympic soccer team from the 1950s. Plenty of nicely authentic surnames and given names will pop up, and a little slicing and dicing will get you a correctly-named supervillain. The great Georgette Heyer derived all her realistically-English titles for the earls and dukes of her fiction by plundering maps — all the names are obscure villages in the English countryside.
Beyond that, the vagaries of naming a character are mysterious — an art rather than a science. My heroine is staying with an elderly Frenchwoman. When the character was named Solange she was tall. Now she is renamed Cresside, and she is shorter. If I rename her again to Yvette she will be shorter yet. How do I know this? Why is it so? I have no idea. At some point the Muse takes charge of the process, and I have to let her do that. A rose by any other name does not smell quite as sweet.
All names, and in fact all terms and invented places, should be shoved through Google. If someone with your hero’s name was just executed in Beijing for sex crimes, you want to know this. You say nobody will likely notice? It is possible you will sell those Chinese-language rights, you know.
Oh, and one more very important tip: when you change her name from Cresside to Yvette, go through the ms with care. Do a Global Search and Replace, but then reread it. There are sad stories about writers who changed the hero from Richard to Wallace on page 200 but didn’t do a Search and Replace. The readers were confused!