Sephlock:
To Ally, you must first:
- research/obtain the "Alliance" tech;
- reach "Close" relations with the target Empire.
At this point, "Alliance" will show up in the Diplomatic bargaining screen as an option. You can offer it just like a tech or TG. Depending on relative size & relations, some AI's might demand extra stuff to accept.
AI Empires will not offer to Ally until you have researched the tech, btw.
To get "close" relations, the most efficient action is to establish multiple trade routes - usually, 3 to 5. It takes a fair amount of time to reach this level.
You can also gift ships, TG's, techs and money to improve relations.
The most important single factor to improving relations is military superiority. AI's will recognize when they are outclassed by your military and voluntarily "improve" their standing with you to encourage trade, etc. rather than war.
Relative alignment is a factor, as well. Opposite alignments will rarely stay at warm (or even neutral) relations. However, alignment spreads of 20-30 are acceptable, with closer alignments gaining better relations faster. To check your alignment rating, go to the "Society" tab under your Empire stats screen (F3).
~SDC~