First, peace treaties and alliances are separate things. You can sign a peace treaty any time you talk to somebody you are at war with... you'll see "Peace Treaty" listed. You may or may not need to sweeten the deal in order to get the AI to accept the deal (conversely, you may or may not be able to extort the AI in the process of signing the treaty).
Alliances are what two civs that are already at peace, and that REALLY like each other, can sign. First, both your civ and the other must have the Alliance tech (not too hard, once you have it, give it to them). Second, relations between your two civs must be "Close" (that being the closest relationship possible). If your relationship isn't close, the Alliance option will NOT appear in discussions with them. Once you get the relationship to Close, you can offer an alliance, and here again, you may or may not have to through something else into the pot to get the AI to bite.
Hope that helped.
- Ash
~SDC~