I agree with many of the things that has been said in this thread, especially with much of what Tomahaha said. Below is a summary of what I look for in allies, how to select them, and how it affects you as you proceed toward the end-game.
You need to converse much with as many people as you can, and more importantly, listen to what others are saying and how they are saying it. With all these chunks of information, you need to form a conception of the overall scenario, always considering the potential ways the game will play out. Next, try to visualize how you might best be able to fit into it, or rather, take advantage of it for a chance to win. By understanding the dangers that each player faces and what they hope to achieve, formulate your discussions keeping those things in mind.
Even more importantly than having successful communication (selling your pitch) with an ally, it is infinitely more important to be able to pick your potential allies correctly- allies who analyze the scenario in the same way you do, and where you all feel comfortable proceeding with a general plan because everyone remains secure and has individual success. However, because things can change so abruptly, it is important to keep as many positive relationships as possible in case you have to change your gameplan.
As the game progresses, sticking with a long term plan for mutual security strengthens an alliance, and I am a big advocate of *negotiating strategic borders*, rather than just trusting an ally and agreeing to dmz's and/or cooperative theatres (even if you both agree to a particular gameplan or strategic analysis, because a wise player knows how to use this against you). However, many times in the early game, a player must take substantial risks with such flimsy agreements in order to provide better opportunities for success. It is important to adjust your style as players get knocked out and your position solidifies.
I rank potential alliances, and consider criteria in such a way that follows:
type 1) A good potential ally is someone you're pretty sure you can trust, and who is attacking somebody else. (a workable condition at present, yet you are uncertain of their longterm goals and/or have infrequent or unstable communication)
type 2) A better potential ally is someone that acknowledges that if they attack you, then it will cost them huge consequences either from you or from other players (i.e. it behooves them to work in accordance with your goals)
type 3) The best potential ally is someone who CAN'T attack you (because you've established a strategic border based on your mutual goals), and attacks other people because it's the only way to go.
Beyond this criteria for finding and selecting allies (with the aim of finding "type 3" allies), an aggressive diplomacy player can capitulate other players, open them up to vulnerabilities, and take advantage of (or stab) the players who lack the scrutiny as laid out above. You'll find that most mediocre players here become content with "type 1" alliances ("type 2" if they're reasonably good), and that is why they always get stabbed and/or are easily tempted to stab their allies.
As the game develops, I am constantly considering candidates for each of these types of alliance, with the end goal in finding type 3 allies. This is why constant communication is necessary in order to review the scenario and find players who share your outlook, (or even better, those who would could most easily gain from you accomplishing your objectives).
Some players out there could choose to play more aggressively- seeking out allies who are doomed to fail in the hopes that you'll be able to capitalize on their defeat, or capitulate their actions. This is a strong technique in some cases, however my preferred style is to make sure that my allies remain happy and in good shape, so there's little chance they conspire against me.
This is very conjectural of course and varies from game to game, but I find it as a very successful strategy if it plays out well. If anything, it's a very good strategy to protect yourself from being stabbed.