Permanent Alliances must be selected in the options list in the pregame menu. The default setting doesn't allow them.

Now, just because you have PA's selected in the menu, doesn't mean the work is done. You still have to cultivate a stellar relationship with at least one civ. I try to stay friends with two civs early to pick the best ally later, or in case the relationship falls apart with one through their aggression or my inattention.  Also, if you choose two likely candidates, they should be friendly with each other or your friendship with one will harm your relationship with the other.

Pick a civ that has the same religion or that you can convert, that improves you chances greatly, and it's best that they not be too close so that border tension doesn't spark "disharmony" before you get to Military Tradition to get a Defensive Pact (DP) or Communism/Fascism for a PA.

Keep your target civ friendly. Give in to their demands. I know what you are thinking... I hate giving into other civs demands also, but if they are friendly previously, they won't ask as if it's tribute, it will be "helping them". That makes it a bit easier to take for me, but it's a fine line. Note: This is a necessary evil to achieve a PA later in the game.

Now... The first prerequisite for a PA is a Defensive Pact. These become available after Military Tradition is researched. Research Military Tradition as soon as possible and get that Pact with one and only one Civ. You must make your choice at this time. A 2nd Pact can drag you into a war which cancels your first pact. (You're DP's are canceled whenever one of the Pact civs declares war on a 3rd party, even if it's because of another Defensive Pact.)

If you and your DP partner have been at war in the past against the same civ, this process is a much quicker one. You'll notice the "Our mutual military struggle brings us closer together" in their +- comments about you. This is the quickest way to a PA later. If you have not been allies in war, you have to have a DP for a ridiculously long amount of time for them to accept a PA. It's not really realistic for you to count on both your civ and their civ staying out of trouble long enough to enable a PA. So, A past "mutual military struggle" should be deemed a prerequisite, although it's possible to achieve without.

Now.. Research Communism or Fascism. Communism is easier and you will likely get their first if you beeline for it. If you have had a DP since Military Tradition and have been warring partners with your DP buddy, then you will likely be able to select a Permanent Alliance in the trade screen when you get Communism or within a few turns of it.

There are three likely reasons why a civ that you have a DP with won't accept a PA right away:

1. "We haven't had a Defensive Pact or been at War against a mutual enemy long enough" (paraphrasing) -  This is self explanatory and I have covered this above.
2. "You're too powerful" - Look at the graph (F9) and change it to show Power. You must not be the top of that graph. That means you can't build a big military. If you did, you can disband units or gift them to your chosen partner or others.
3. "We're doing fine on our own" - Look at the Power graph again. You're chosen partner must also not be on top or you get this problem. This means you probably can't gift him your units. If you didn't give him any and he's still on top, then you have to give tech and possibly units to another Civ. One that you don't plan to attack probably. Just a few units makes a significant jump up on the Power chart.
   

Once you have the PA:

You can open their city screens to view culture, build list, etc. Your workers can improve your PA civ's land. You can tell your PA what to research and which city to attack. You can ask for, and get, any and all resources. However if, for example, you take the only Horses, you're partner cannot build cavalry.

Your partner will share any victory or loss. If anyone declares war on you, they are declaring on your partner also. If you or your partner declares war, the other is automatically involved.