In Europa Universalis II, the Treaty of Tordesillas and the subsequent Treaty of Saragossa were two agreements in which the Pope divided the non-Christian world between Portugal and Spain. In history, the Treaty of Tordesillas happened in 1494, and Saragossa in 1529; see the wikipedia entry for the Treaty of Tordesillas. In the game, the effects of the two treaties are abstracted into one.
In the game, Tordesillas randomly occurs between 1505 and 1518. Specifically, it happens on one of the 5000 days from January 1, 1505, to October 20, 1518 . It is in effect whenever both Spain and Portugal are in the game, so long as both countries are still Catholic or Counterreformed Catholic. While the Treaty is in effect, Spain and Portugal each have a defined area of the world that is "theirs". If a Spanish or Portuguese army encounters any foreign army (Catholic or not) in its area, a battle will result.
Basically, Spain and Portugal are in a permanent state of war with any foreign Catholic-owned provinces in their respective covered area. They may enter "their" provinces with land units even when at peace with the owner. Trading posts and colonies are captured immediately unless battle is offered. If there is a fort, Spain/Portugal will cover it or seige it with enough men. Ownership is immediately transferred if they capture any Catholic-owned province. When a province is taken in this way, the former owner gets a 1 year casus belli against the taker.
The Treaty ceases to function upon the Edict of Tolerance event, circa 1650.
Spain's area contains Mexico, the southern USA, most of the Carribean, the Incan areas and a few islands in the East Indies. Portugal's areas covers Brazil, all of Africa south of the Sahara, India, and the East Indies. Unaffected provinces include Canada, the northern bits of the USA, and some islands. You can see the covered areas graphically on the colonization map: provinces affected show a small icon for the relevant semi-owner.
The following maps show the Tordesillas provinces in each part of the world. Spanish provinces are coloured yellow, Portuguese are coloured green. One Tordesillas province is not shown on this map (the Azores - which begin the game owned by Portugal anyway).