Diplomacy for Dummies
By Wouter Snijders

It's very important to always approach to AI in the right way, by being Obsequious/Meek, or optionally (once on good terms) Friendly/Equal. Unlike what one might expect, it's not true that the Magnanimous/Kind is the most friendly tone of voice and the Hostile/Angry the least friendly with the others lying in between on a linear scale (I originally thought this myself until I reread the manual one day (p. 57 "Sending Diplomatic Messages")). 
Also, be generous if an AI doesn't like you very much, by giving gold/maps/advances often (I've found that it's generally better to give small gifts often than to give big things only occasionally). If you're on good terms with an AI, you don't need to be quite as generous but an occasional gift is useful to maintain that good relationship. 
Agreeing on any proposal the AI makes, or at least countering it by something reasonable, helps a great deal. Of course, holding receptions, establishing embassies, trade and building diplomacy-wonders helps a lot as well. Getting any kind of treaty ASAP is very important as that raises trust quickly, which of course makes future negotiations much easier. 
In case of a trade, always make the request first and the offer second, the AI seems to see the second part of the message much more as a supplement to the first part than as as something on an equal level. A trade maps proposal with the request part first succeeds much more often then the same proposal with the offer part first. Also, all his counter-proposals are based on what your first clause is (so, if you offer your map and request 200 Gold, it might counter with asking for your map in exchange for 100 gold; if you request 200 gold and offer your map, it might counter with giving 200 gold in exchange for Bronze Working). I never saw an AI counter an offer (don't offer very much, so that might explain it at least partially) but countering requests is not unusual. 
Threats can be useful as well, if you have a large army near one of its cities it is much more likely to agree to something if you threaten to destroy that city, regardless of your relationship with it. If you're on good term with an AI, threatening with war can get you what you want as well, even if you have a relatively weak military. Against an Ai who's already pissed of at you it won't make much of a difference. Threatening hardly seems to cost any regard or trust, so threats are harmless as far as future negotiations are concerned (though I don't know what the effects of excessive threatening would be). 
The best way to deal with the AI early on depends on it's personality type and it's stance towards you when you first meet him (some AIs start out respecting, others disliking you). The best start is always to suggest a exchange of maps as soon as you meet, it rarely refuses that if you do it in an obsequious way and it immediately likes you more for making reasonable proposals. Then a gift of 100-500 gold (depending on the size of your treasury and the age) is a good second step (do it in the same turn if possible). Depending on how much it likes you, either a Peace Treaty or (if that's not gonna work) a (mutual) Tresspassing agreement is a next step. Once you have a Peace Treaty, only doing things that are plain stupid can ruin a good relationship, things like breaking agreements, frequently demanding unreasonable things, continuous tresspassing (even if you don't have a tresspassing agreement), unconventional warfare, commiting atrocities (even against mutual enemies), etc. If it's not likely to sign a peace treaty or if it rejects it (FE because he's an Agressive Imperialist who disliked you from the start), things are a little bit more difficult but by frequently giving gold/advances/maps and agreeing to everything it asks you (within reason of course), good timing and most important of all, lots of patience, you should be able to get him to sign a treaty at some point. After that, it might still need more attention than a Diplomacy-minded Peacemaker, but it should be quite possible to exchange maps or techs with it or to get it to sign a Trade Pact, Military Agreement or even an Alliance. 
In my experience, diplomacy in CtP2 requires more effort than in any previous Civ-game but it's much more interesting as well, esp. with the Diplomod (for me as a peaceful, diplomacy-minded player probably the single biggest asset of the entire MedMod). It's also very rewarding to see your efforts actually paying off in the form of a Diplomatic Victory with still 4 or 5 Civs in the game when you started out with 6.

WW Note: I tried out Wouter's system, and it indeed worked as well as he said it did. I recommend everyone follow his example for games with greater enjoyment and less frustration.