How to create interesting NPCs and compelling relationships

Well, I´ve read here recently that at least other MC has trouble creating PC-NPC-PC triangles, interesting and compelling relationships, antagonism and drama sources between the PCs in the fiction, etc.
Well, I sort of have trouble with that too, but I´ll explain why because it is a particular issue:
In my campaign, the group´s got a mission related to travel to other holdings to gather a debt, look for a missing cargo, etc. I had struggled to build an interesting relationship map within the first holding: Awkward, but then they started to travel to other ones and I found it difficult to extend the relationship map outside the first holding.
I tried, anyway, to resolve it, by creating NPCs connected to the PCs on the fly, as I needed them. And the way I did it was by creating past relationships with the PCs, like this: "White was hired by the gang you´re about to fight against; he´s a colleague of yours, and you´ve worked alongside with him sometimes" or "To find Hugo, you shall get Shazza´s permission first. She was Melody´s (PC) best friend while they were child, but then they grew apart, as Melody didn´t want Shazza to start working as a prostitute. On another subject, Doom (PC) also knows her, he spent some nights with her while he was travelling or being hired."
Is it right to do this a lot, create background or past information for the PCs? Or the relationships should always involve things that are happening right now? Should I have already a list of Melody´s friends and partners, Doom´s colleagues and employers, etc., handle it to the players and start using them as the campaign moves on?
Another possibility is to handle that by asking the players themselves: "You already know her, how did you get to know her and what were you doing then?", but I fear that sometimes the players might not involve their PCs in the situation too deep "Just worked once with her, nothing important".

I´d like to get help with this, because I´m acting here out of "instinct", but I´d like to have some principles to guide me, and I can´t relate the ones AW has to what´s happening.

Khimus,
Sounds like you're doing a lot of the right things. Perfectly fine to make up that stuff on the fly and present it to the characters, or let the players answer your questions. Can also use "love letters" as a way to bring the story. But some things do occur to me:

You didn't make any mention of fronts or threats. Those still apply out here and should be making their moves. You can announce badness back home, bring elements of the front out wherever to confront the characters and make their moves, introduce new elements of existing fronts or create new ones.

- "You work for Kipper?  That old man?  How is that possible? He died last year miles from there, saw it with my own eyes.")
- "Oh you're from Boxtown? How's my brother III?" ((shit, we beat the shit out of III last week)) "er... he's fine..."
- Funny you guys were sent here by Kipper to deliver the goods to Damson. Thing is, nobody out here seems to have any idea who Damson, or Kipper is....   shit... why did he want us gone for a week?
- You open your brain to the the psychic maelstrom... expecting to find out about these mud flats.. but all you can sense is that kid, Trace, back home, screaming.

But really... sounds like you're doing your best to introduce relations on the go, which is great. These characters weren't born the moment the game started. Completely reasonable that they meet up with people. They won't find them all compelling, hopefully some. 

How about something like this:
MC: "So there's this girl Trace, she looks upset and she looks at you with a glimmer of recognition, how do you know her?"
PLAYER: "Oh...  just worked once with her, nothing important"
MC: "She approaches, pulling a knife. You fuck...  where the hell were you all this time?  I thought I meant something to you!"

The principles are there to handle the road. It's harder than staying put for sure but really AW handles it. So many mobile playbooks, it has to.

Hope that's some help, I have a driver in my new game and I'm going to have to deal with this kind of thing too, soon.

Keep in mind that these players are looking for the same thing you are: hooks that make them care about the situation at hand.

Thus, you can always turn to Melody and say: "Shazza... you used to know Shazza, didn't you? How do you know her, and when did things turn sour?"

Asking questions like crazy tends to more reliably create compelling hooks, when the questions are pointed, than just telling them how they know Shazza & Co.

I think the best way to get PCs involved is to solicit something from the players.  When your player says "we used to be lovers" it's a lot more powerful than if you say it.

I also have trouble getting my players to commit.  (They do the "oh, I did a job with him, one time" thing.)  But I give feedback ("that's good, but it'd be more interesting if you had a stronger connection.  What if something important happened on that job?") and we're slowly moving in the right direction.  So I encourage you to try to get the players to invent the backstory as much as possible, but push them to take chances when they do it. 

Give the NPC a straightforward, clear, powerful emotional response to the PC. A kiss, a punch, a long hug, bursting into tears, a huge sigh of relief, fight or flight.

I actually got a lot of inspiration from the Dogs in the Vineyard rules - specifically the advice for how to play the townsfolk as GM in that game, where you should note what the different NPC's want from the Dogs.  So when I'm making NPC's, I always try to note what they might want from the PC's, and it's usually something pretty concrete -- help me take over, kill my enemy, sleep with me, keep my baby safe. 

Also, I try to make the NPC's grabby by latching onto details that have already been established.  But I think you have to play fair, even in AW, and let some of those hooks be positive or neutral, otherwise the players will assume every NPC is trying to get them killed.

And I try to make them simple and memorable, like characters in pulp fiction. My Rolfball dresses like a businessman, talks like a hippie, and has a horrible skin disease.  He's a simple guy who's motivated by greed and tries to make bullshit business details whenever he can.  If somebody reads a person or the Brainer scans him, I guess I'd have to delve deeper into his background and flesh him out more, but he's pretty functional as he is.

And, you know, sex.  I borrowed an idea from Vince in the first session and said to the players in effect, "You know that old guy you were sent here to rescue?  Well, he's got a young daughter and she's really hot."  And that's worked pretty well -- nobody's fighting over her yet, but people are making promises and setting up future trouble. 

Finally, I find the read person and brainer moves are really, really powerful for making NPC's come to life.  Also, if somebody fails a read person roll, be sure to ask the player a question that that NPC would want to know -- mostly it's "are you telling the truth?" or "how can I get you to do X?", where X is something totally outrageous. 

In my game, the PCs have recently become fairly mobile, and I faced a similar issue of extending the freshly burgeoning NPC hooks to still matter far away. One technique I stumbled across whilst writing out my fronts (especially dark futures) was to give a number of already introduced NPCs wider interests than I initially thought. So, Dice, that guy who runs a stall in the market? Turns out he's ramping up a regional drug trading network, and he wants this guy in that other town dead, so he hires the new battlebabe to do it. The PCs who pissed off the hardholder by beating up one of his gang members? They can only make amends with him if they somehow cow the holder who's supposed to be sending in tribute from the town with the rival drug dealer. Not so important when the PCs only hang in one town, but it saves you a lot of work from coming up with all new people and threats and fronts for each town if a lot of them have hooks wherever the PCs happen to go.

Oh, and gypsies. I have winnebago driving gypsies in all my games. They can be wherever the characters are, and they're already familiar :)

I'm a player now, and I metagame this. If I can start a small rivalry with another PC while keeping my character real, then I will. Nothing out and out unless it calls for it, but maybe I decide I like the same girl as Fox does.

And try and make sure the PCs don't travel alone. There should be some NPCs in that band as well.

In a lot shows where the protagonists travel, there is a focus on interpersonal issues, with what happens in a town being the monster of the week.

Like someone else said, Dogs is good for this.

Explicit triangles, as an MC. If it helps, write them down, or make the relationship a stake.