Passports are now considered an essential part of international arrangements, functioning as travel documents, proofs of citizenship and rudimentary universal identity cards.
The idea of a document of safe passage granted by a sovereign is ancient. There are some suggestions that in ancient Egypt, citizens carried the name of the Pharaoh with them abroad, possibly as a warning to foreigners that they were members of the regional power.
There is a biblical reference to something like a passport being granted to Nehemiah by King Artaxerxes:
Nehemiah 2:7,9
... I said to the king "If it pleases the king, let letters be given me to the governors beyond the river, that they may convey me over till I come into Judah... Then I came to the governors beyond the river, and gave them the king's letters.
It seems that occasional passports have always been issued on an ad hoc basis by monarchs to travelling subjects.
However these are unlike modern passports, and perhaps more like ambassadors' credentials.
In 1415, King Henry V granted Safe Conducts in an Act of Parliament to English travellers, asking for protection for bearers, and threatening anyone who messes with them. These were granted to foreigners as well as Englishmen. Similar arrangements were made by other countries of the time.
The first passports as we know them today were, unsurprisingly, French (the word passport is derived from Fr. passe port, a port pass). King Louis XIV, in has determination to be an absolute ruler, made it illegal in 1672 for people to leave or enter France without his personal agreement. Other countries in Europe reacted reciprocally, so that within a century almost every country in Europe had a passport of some kind. This grew up hand-in-hand with a system of a host country requiring visas for travellers coming in.
For a passport to be useful it had to contain some details about the bearer to prevent theft and forgery. This meant that passports were immediately able to serve other functions than simply travel. The Russian empire from 1719 used them internally for taxation and military service. They effectively became internal passports, and were sometimes needed to travel between cities.
Just as France led the trend for passports, it was also the first European country to abolish them, in 1861. They were seen as an unnecessary impediment to free travel in the more peaceful Europe of the late 19th century. Most of mainland Europe abolished passports so that by the beginning of WWI, there were few tight border controls.
With the advent of photography as a cheap way of determining identity, passports began having photographs attached to them in the early 20th century. This become more important during the First World War, when countries began reintroducing passport systems (some places, like the UK, never abolished them in the first place). By then, passports had all the essential functions that they do today; they were useful for knowing which of the refugees created by the war were genuinely citizens of the country they were trying to enter.
Most passports were printed on folded paper until 1920, when the League of Nations held an "International Conference on Passports" in 1920. They established general guidelines for standardising passports, which recommended that they be in booklet-form, with a photo and some form of security. This enabled visa stamps and other details to be put directly on the passport. The photograph and personal information (such as date of birth, nationality, place of birth, passport number.
Nowdays, every country (AFAIK) issues passports and requires them -- to some degree -- for entry. Some borders that used to require passports no longer do; you can travel throughout the Western Hemisphere (except Cuba) on a driver's licence or other less-secure identity documents, and a similar arrangement operates inside the Schengen Countries of the European Union. However, liberalising and tightening of borders seems to be a periodical thing, changing every fifty years or so. The US-Canadian border, like Europe, is a good example of this.
We are due a phase of border-tightening, and this one will be largely in response to fears about international
terrorism (for the USA) and
asylum seekers (for Europe). There is already talk about more controls on the Western Hemisphere passport exemption.
One thing that has tightened significantly is recent years is passport security. As a holder of a passport can usually use it obtain all other forms of identification, passport theft and forgery are more serious now than in the past. To combat this, modern passports tend to have printed and laminated photos, holograms, watermarks, machine-readable data and other difficult-to-falsify features.
Obtaining a passport is also more regulated in most countries. In Europe, the USA and other 'developed' countries, passports are cross-checked against births, and applications (and photos) need either cast-iron documentation or an identifying witness. In the USA, passports must be applied for in person. Passports also expire and need renewal after a certain period of time; in the UK, this is normally 10 years. In the past, family passports were common, as was having young children named on the passport of a parent. Passport authorities are dispensing with these rules and beginning to require one passport per person, even children. This is in part to combat abduction of children by a parent during custody battles.
http://www.ppt.gc.ca/passport_office/history_e.asp
http://www.readersdigest.co.uk/mfacts/webfacts/3263BB69A461B53A80256A950039C526
http://www.stetson.edu/~psteeves/classes/louisxiv.html
http://www.ocma.gov.lv/?_p=337&menu__id=13
http://homepage.uvt.nl/~s498467/scriptie/3-1.html