you pick whichever one you think gives you the best chance of winning or being part of a draw, cross your fingers, and hope for the best =)

So you adress only one candidate at a time and if agreement is not met pick another?

If you speak softly (hiding your big stick), then no particular alliance needs to be mutually exclusive.

In my games I try not to make promises that I can't keep, and I generally play as honestly and openly as possible.. because that helps people trust me even if we're more or less forced to be enemies at that particular moment in time.

Obviously, if your options are only:
"Hey france, I'll support you into Hol against Germ"
and
"Hey Germ, I'll sup you into Bel against France"

then you're pickled..
But if you can try to keep options open and semi nebulous, you can fish to see who will make the better ally in the short and long term based off of how they choose to reply.

I usually wait to be contacted to avoid that problem.

^In other words:
I would not suggest that you ignore one player while trying to build an alliance with his (possible?) enemy. Among other things, your silence just indicates your preferences and/or hostile plans.

Nor should you try to make explicit promises to each right from the start, as that may force you into a betrayal too quickly.

Obviously, if your options are only:
"Hey france, I'll support you into Hol against Germ"
and
"Hey Germ, I'll sup you into Bel against France"

---

This is where you support Ruhr into Holland and go 'whoops!'.

Ok, Mr. Pinguin, I see your point. It's not always possible to be vague though: sometimes situation calls for immediate specific arrangements, I guess.

Xapi: that is definitely a conflict-free strategy, but a little bit passive, don't you think so?

SoroSuub1: and then France and Germany are both mad at you and jointly attack :)

There is no such thing as mutually exclusive allies.
Even if they are fighting each other they can still both be your ally as long as you are careful to avoid being in the middle of things.

I don't like waiting for others to come to me, I am usually the one who tries to talk to everyone as early as possible.
That's because the first one who makes a reasonable proposal is the one who gets considered.

especially in the first year, you have to make yourself seem to be a lucrative ally to everyone, so that everyone is interested.
When everyone is interested, you have the freedom to choose.

If you only talk to one possible ally, always keep in mind that the ally you*didn*t talk to may very well has talked to you ally. And that now, the only one who has the freedom to choose is your ally. And that might easily end up very badly.

Always send messages to everyone immediately. You can talk the talk with everyone and not seem like you are screwing them immediately. As Turkey, you can suggest a bounce in the black sea with russia and then promptly promise Austria you will open to the black sea and ask him if he can convince Russia to make it a dmz. Your moves will betray no one: they both expect you to open to the black.

And I 100% agree with Akroma, especially on not talking to one ally and then they petition your chosen ally.