This is what I try to do step by step.
1. Research the diplomatic relationship techs ASAP. The mutual +3 relationship (assuming the AI gets it also) is a must.
2. Find a player you know you won't ally with (Because it's TEC Rebels and you're not TEC or its in your way) and try to blow up as much of his stuff as possible. Military relations are the foundation of most alliances. The more damage you do to a mutual enemy the happier everyone else will be.
3. Try to get a trade agreement ASAP. You should get a slow but steady increase in relations after it based on your number of trade ports. It's a great stepping stone to a cease fire.
4. If an AI is close but not quite at a level for a cease fire, sending gifts/tribute/bribes, whatever you want to call it, is a great way of speeding the process up.
5. Once a ceasefire is signed, immediately follow up with an envoy cruiser or two and you'll probably be allies for the rest of the game.
Another thing that trips people up is that you (your faction) have to like the player you want to ally with as well. If someone has just finished blowing up one of your planets, your people aren't going to like that very much, so it may prevent you from allying with AI actively attacking you. Generally its easier to get the AI to like you then you to like it, but eventually some AI kills enough enemy ships to let you get a trade agreement and then cease fire.
