It really depends on the story and what kind of mood I want! If Im writing something spooky, I'll name it right away. Fantasy is an iff because I have to search for a name. Or sometimes, my characters have no names because they've been lost through time within their story and is referred by a title.
i give them bad placeholder names until i get better ones and then end up getting attached to the placeholders
alternatively, as with my character jack: forget his name was supposed to be jake and get attached to the Bad Memory Replacement
Much of the time I'll do research. In recent years Behind the Name has been my go to site.
Other times I'll just use whatever name pops up in my head.
But they always have to fit the character that I've already drawn out/envisioned in my head. I don't think I've ever had a name first and created a character around that.
I'm with @Ringarune here - same with me =P
I first create the character, what's he/shes personality? Looks? Life/Past? Then I give them names. I useally do go to http://www.behindthename.com/1
from there I choose the names orgins, how it match with the character. Whats the names orgin?
If I dont find any I like then I combine two diffrent names and make it sound right. That fits more with Fantasy-names
I just kind of choose names that sound good. One of my characters has a name that actually means something and the rest are chosen just for kicks.
(Actually for one of my characters I asked my jazz teacher to say a random last name and assigned that to him lol)
Most of my stories take place in an alternate earth - very similar to our own.
Therefore the name choosing consists of searching nice sounding names in different languages, depending on the characters background and ethnicity. I also lookup the meaning behind the names - coz y not 
Examples :
Salvatore Marchesi (italian dude)
Jinan GÖKÇE (turkish girl) - goes by Jinny
Eutychia Kosmidi (greek girl) - goes by Efi (pronounced Ehfee)
For me its not what i like, its what i want to tell the reader. The name should be apart of the story, not just something i like.
I grabbed letters, and put them together... this did not always have the right effect..
once i had a character names: Porgasius....
-Google names and then look at what they mean
-Name that I like and look up similar names
I try to look for names that are easy to say/ sound nice and suit the character personality
It depends on the characters importance for me, so if it's a main character or one who's got a big part usually design and personality elements come first then find a name that fits. Some cases a character goes without a name until some of the story or background about the particular characters been written. Other times I'll just pull a random name out of a hat and that's it.
There's also throwing an arrow blindly at a dartboard but only if naming has gotten boring, or it's become too difficult, does that option come up =w=)
I do that too, I give them titles based on the things they do. What I do is imagining myself as a random bystander or a person witnessing them for the first time, whatever pops up in my head will be their nickname.
Like a girl who can transform into a powerful magician that mainly harnesses the power of fire, along with her transformation her black hair turns red and her brown eyes, crimson. My first impressions were "Crimson mage" or "Infernal Flower" But then I remembered that this particular character was a maid. So it hit me, "Blaze Maiden"
I'd give them names afterwards, but I focus more on their personality and backstory first. After I've finalized that, I'd poke google to give me a list of suitable names for them.
Depends on which story and what they need to be.
If it's a just on Earth or if it works, stuff like Steve.
If it's in a fantasy setting, I usually just type gibberish or break out google translate and find the most exotic words.
I gotta have names early on. I don't feel right referring to characters as "the tall blonde one" or some such. I also feel like having names helps me with character development. It's much harder to name a character that's fully fleshed out, rather than a fresh new character. I really struggle with names anyway though, so I always tell myself the early mediocre/terrible name are placeholders. But 9 times out of 10, I get so used to using those names, that I never really change them. If I try to change them, I end up constantly switching back to the old name on accident.
If I'm determined to have a great name for a character, I'll ask my partner, and he'll let me borrow a super cool unique name from his pool of potential character names. Feels bad stealing a name from him though lol.
I can totally relate to OP!
I have characters who are supposed to made their appearance in a few pages and one of them still named "équipier" ("male teammate"). The others two have just been name but are referenced in my scripts as "équipière n°1" and "équipière n°2" ("female teammate n°1/n°2"). XD
I'll say gibberish and hope it sounds cool. And bam! We got a name. Also I try to avoid names of people I know irl cause it feels awkward to me.
Sometimes it's random names that I like (Pablo, Gilbert, Lucy, Jane, Jade.), sometimes it's pun names, (Lord Tiberius Claudius Nemo, Fugo), and sometimes it's made-up names that are just random stuff thrown together/from a dream, (Cordensia, Ardella, Tintom).
As most of these guys said, I usually come up with a personality first and find a name that fits that characters. I try to look up the meanings of the names and if it clicks in my head and feels good then there we go. Other times names come from people I know in real life.
In high school I knew a girl named Jamie who was really pretty, bubbly and overall a really sweet girl. So when I created a character who was bubbly, cute and nice, the name Jamie popped into my head immediately and it just felt right. And then sometimes it's just random. I had a character named Tyler once and it never really felt right but I kind of just rolled with it, until I called him Ryan in my head by accident because I was talking to someone named Ryan earlier and it clicked immediately. Like he was obviously a Ryan, not a Tyler, how could I be so blind?
I wing it -- plain and simple. Only few characters I've made have meaning to them. A lot of times, I use Behind the Name as my source of getting names. Of course, I also like to make sure the names fit the time, era, or culture the characters are in. But after that, it's fair game.
If I like several names for one character, I usually do a blind pick and keep the rest for later. Or, I choose a random number between 1 and 26, find out which letter that is in the alphabet, and then choose a name that starts with that letter.
Though, I think that's akin to a parent naming their kid because they like the name, you know? Sides, not everyone represents the name they're given. I've know a person named Gaia -- which means Earth (a generally down to earth person). She was NOTHING like that.
I say go with your belly-gut XD
.