You need to have 'Close' relations--no less will do. Once you have that and Alliance tech, you should be set. If there are any negative factors listed on the foreign relations screen, you most generally need to eliminate them (if possible) in order to reach Close relations.

Thank you for mentioning this part about trading the other guys the alliance technology. Once I did that, I was finally able to form alliances. I didn't see this tip in a couple of the other forum threads on this topic.

Not necessarily. The trick in that case is to play part of the game like a military conquest scenario. You'll have to do some fighting until you're down to the factions you really want to ally with.

The others will pick up the Alliances tech eventually. What you need to do in the meantime is build up a military rating that is greater than any of theirs. This will make them much friendlier and more willing to bargain with you. That high military rating will also improve your score.