God I love that game. Anyway, you can't really sign an alliance as you can in civilization 2. You can ask for a military pact against another nation, which is basically just asking them to declare war on someone else. You can also ask em to have a right of passage with you which lets you move troops on their lands (and their troops on your lands..). There both done through diplomacy, there should be an option on there somewhere (and if theres not, you don't have enough tech to do it..)
Oh... and if you want, go
here and go to war academy. Theres a ton of strategy guides and tips there.. i'm godlike at civilization 3 thanks to that site o_o