Negotiating looks like a big part of this game (playing my first game this weekend) - but what sort of limits are there to this? For instance, are armies allowed to march through players territories without attacking each other?
Nope - no marching through each others' territories. You also can't trade power.
However, you can make any promises you want as to what you will/won't do. But you can't alter the game rules with an alliance.