Here are some things to keep in mind!
Make the name pronounceable. It’s annoying if the reader has to sort of mumble over the name in her head every time she comes across it. If you’re writing something historical, try to find accessible names that are still historically accurate. Áed and Máel-ruanaid may have been popular guys’ names in early medieval Ireland, but readers will probably feel more comfortable with Conall or Dáire (and you may not feel like you want that accent mark.)
Make it believable. If your characters have to discuss the name at length (“Why did your parents name you Devyl?”) consider the possibility that it’s too far-fetched. You might like to balance a more unusual name with a boring last name (Indiana Jones), or vice versa (Mary Poppins). If both the first and the last name are fanciful and evocative, the result can be eyeroll-inducing (Bella Swan, Anastasia Steele.)
Of course, you have more freedom with non-human beings. If you have, say, one supernatural or otherworldly character and one “everyperson” character, the names can reflect that dynamic.
Here are some good resources for naming:
Social Security Baby Names site
For the years 1880 to the present, you can pull up lists of the 1000 most popular names for girls and boys in the U.S., respectively. Figure out what year your character was born, and pull up the list!
This guide to naming a pet happens to be one of the best character naming sites out there for paranormal, historical, and fantasy stuff. Whether you’re looking for angel names, Gaelic and Celtic names, nature names, Maori names, or whatever, you can find a great list to choose from here.
Last names, U.S. Census Bureau
This is just a long ugly list of last names in the U.S. today, arranged by popularity.
Make the name likeable if the character is supposed to be likeable (and unlikeable if she’s not).
babynames.com has a rating system for names, so you can double-check and make sure you haven’t picked a character name that will make everyone hate him or her immediately. Just search the name and look at the star rating.
Avoid making non-European names too stereotypical.
If you have a character who is American-born Chinese, for instance, maybe don’t name her Jade Choy just because you have a Chinese-style jade necklace and you use La Choy soy sauce. Do your research.
Make your character names different enough from each other.
If you use the same start letter for a few different characters, your readers may get them mixed up. Sometimes the same start letter can be a good way of identifying siblings, though.
Don’t give all your characters’ names the same rhythm. If everyone has a two-syllable first name and a two-syllable last name, it’s going to start to sound weird.
Avoid choosing names that contain a lot of the same sounds, i.e. “This is the story of three friends: Dan, Manny, and Randy.”
Just a few more notes:
If you’re writing fantasy, think about giving all of the people of the same non-human race a similar logic to their names. For instance, if they’re fairies, you could all give them names inspired by nature, or if they’re aliens, you could start with ancient Sumerian names and alter them all a little, or something like that.
You can change what your characters call one another to indicate an increasing degree of intimacy, as when Dean in Supernatural first calls Castiel “Cas.” It’ll give everyone a little thrill!
Finally, before you use the name, Google it to make sure you haven’t accidentally come up with something that belongs to a famous real person or well-known fictional character.
Now that you’ve got the perfect name, you can go on to create an amazing, immortal character. Hooray!