Giving a character a name is simultaneously one of the simplest and yet the hardest tasks in writing a story. It's simultaneously very important and yet rather trivial. That said, picking a good name for a character is one of the simplest ways to avoid the Mary Sue label.
Necessary TropesAbove all, a character's name must be appropriate to the setting of the story. There weren't any Victorian British teenage girls named Sakura, there weren't any Native American princesses named Krystle, and there weren't any samurai warrior girls named Cindy Mae. Those characters, especially if they are the protagonists, scream Mary Sue even before they open their mouths.
Let's divide a couple of "appropriate names" into a couple of categories.
FanficThe key to naming OCs is to notice patterns in the canon characters names and above all, stick to them. If the canon Magical Girl squad consists of Rose, Poppy, Ivy, and Violet, Daisy would be an appropriate name for an OC, Megan not so much. Canon characters in The Hunger Games universe usually have names that relate to their district or Roman names in the Capitol, Harry Potter characters often have Alliterative or Meaningful Names that often have a whimsical feel. Persephone Starflower and Winnifred Wiffleball would both make acceptable names in a Harry Potter fic, albeit Persephone would probably be in Slytherin while Winnifred would be in one of the other three. In a Hunger Games fic, Persephone Starflower would be okay, if a bit on the nose, but Winnifred Wiffleball would be completely out of the question, while in a Mary Poppins style work Winnifred Wiffleball would fit right in and Persephone Starflower would be out of place.
HistoricalIf your work is set at some point in the past, research, research, research. Look into the sort of names that would have been popular at the time and place of your story. Going back to Victorian Sakura, figure out the year she was born. If the story is set in 1898 and she's sixteen, she'd have been born in 1882. Don't look up popular names of 1898, look up popular names of 1882 (this is especially important if your character is over 30). If you still want to give your character a name that stands out, consider using a name that was popular at the time but has fallen out of fashion. Mary, Elizabeth, and Margaret were popular in 1882 and still are. Henrietta, Myrtle, and Philomena are rare today, and have a distinctly Victorian feel, and while today they seem stodgy, they are also very distinctive without having to name your character Sakura. (Oh, and if your characters were born in America since 1880, the Social Security Name Database is your new best friend.)
Future or DystopiaHere you have a lot of leeway. But think for a moment about what kind of society your future/dystopia is. Has mankind gone back to a predominantly agrarian society? Maybe more nature-based names come into style, like Oak, Rock, or Storm for boys or Hyacinth, Azalea, and Citrine for girls. Has society tried to rebuild ancient Rome but with sci-fi technology? Names like Julius, Minerva, Juno, and Aeneas would probably be really popular. Also, if your story is set Twenty Minutes In The Future and your protagonists would probably be either alive now and very young or born within the next couple of years, again check out the Social Security name database (again, only if your characters are American) for what year your character would have been born (or if they aren't quite born yet, keep your eye on some trends.) If your story is set in 2045 and stars a thirty-year-old, your character will be one-year-old now. Even if society had returned to ancient Rome, your leading man would be more likely be named Liam than Romulus (unless he changed it, and even then he would still have Liam on his birth certificate.)
Modern Earth as it isYou have a lot of leeway here too. Few names are truly off limits; beware of giving characters names of ethnicities they don't belong to - don't name your white characters Sakura, it kind of reeks of Unfortunate Implications. That said, it also kind of spurs diversity - if you find out that a surname you like for a character is Bulgarian, why not make that character Bulgarian?
- Awesome Mc Cool Name or Special Person, Normal Name? Awesome Mccoolnames are obviously awesome, but sometimes they can be a bit obvious. Whether this is better than a more normal sounding name depends on the style of the work. If the work is going for a bombastic epic feel a name more glaringly awesome might suit the character better, but if the story is more down to earth with an Everyman protagonist then probably go with Special Person, Normal Name.
- As a rule of thumb, avoid using your own name for characters at all costs, especially leads. If your name is Emily, for instance, then I'd advise you stay away from Emma, Millie, Amelia, Emmett, and Annalee too. It's one of the first major signs of a bad Author Avatar.
- Be wary of Famous-Named Foreigner. Keep in mind that One Mario Limit often applies if a person with a very distinctive name rises to power or becomes popular. Even at the height of Napoleon's power the name never really caught on. That said, at the same time, sometimes the exact opposite is true - many names become popularized by pop culture or politics. Check this out on a case by case basis.
- One Steve Limit. It is your friend. Yes, many people in Real Life share the same name, but unless the fact that two characters have the same name is a plot point, as in The Big Lebowski, or a gag, avoid breaking this, including My Nayme Is variants.
- Go against some long standing stereotypes of a name. Make Harriet a bombshell. Make Hans a good guy. Make Archie a muscular bruiser. Go wild!
Suggested Themes and Aesops & Potential MotifsTheme Naming! The regulars like Floral Theme Naming, Rock Theme Naming, Religious and Mythological Theme Naming, and Colorful Theme Naming are fun, but try some new themes, especially subtle ones that border on Viewers Are Geniuses.
- Be careful with Alliterative Theme Naming. Remember the One Steve Limit and the fact that it is your friend. But Alliterative Theme Naming can be done well, as long as none of the names step on each other's toes. For instance, in Neil Simon's Rumors, it's a gag that all the women in the plot have a name that start with "C" - Chris, Claire, Cookie, Cassie, a middle name Clara and a minor character Connie. Note that the names have differing numbers of syllables, and barring Claire and Clara none of the names have the same root. If your leads are Tommy, Timmy, Toby, and Tammy people will get confused, but Tommy, Tatiana, Teresa, and Tim are different enough that the audience won't be so muddled and yet still get the point.