I play very straight-forward. I offer to ally with everyone I can and see who I believe the most. I also try to put myself in the shoes of the other guy and think "what would I want if I were him" and I try to offer him that very thing. I've found that alliances are based almost solely on gain. The other guy isn't going to want to work with me if he has no room to grow. Once he quits growing, he will then think about if he can move over top of me. Thus, I try to lay down a plan of action that will suit the both of us. I try to be honest and upfront. There's little use lying early on. I'd say that I tell the truth 90% or more of the time and lie 10% or less of the time and when I lie, I make it count.
Second, I work to lead. I present concrete plans, a direction forward and clear thinking. I find that a vast majority of people tend to follow and they "cling" to leaders. When I offer a solid plan, it shows someone I'm interested and sincere and that I've spent some time in our present situation to think through things and develop a plan that includes US, not just me. People respond far better to this type of press, rather than "hey can we bounce here?" or "I'm interested in ____"
If, at the end of 1901, I have no allies, I move on to their neighbors and make allies with them. If I'm playing as France and I'm being attacked by England and Germany, then I make friends with Russia and offer him whatever it takes to apply pressure on some country until they want to be my friend. I've found that in this game, it's good to make sure that everyone stays busy, and that the busy-work shouldn't be you.
Last, if I think that things are going sour, I find someone I can trust and offer to get them an ally if they can do the same for me in return.