Give them money and technologies. If you're playing Multiplayer Gold Edition, you'll want to do this on the turn you initiate contact (since they'll quickly become hostile after that). If all you need is a general location for the civ in question (so you can send caravans), a single map exchange is usually sufficient. Delivering caravans can also increase attitudes, I believe.