Related, when and how did the concept of citizenship become standard? When was it that people couldn't just travel to another country, find work and settle down without needing permission from the government?
The League of Nations - 1920.
Before the twentieth century, global identification is extremely complicated and generally geographically specific. We have the issuance of letters of passage all the way back to the middle ages, and early passports being given to ships for travel rather than individuals.
Nonstandardized passports began to be issued more to regular citizens in the mid/late-1800s, then became of special importance as needs to control borders during World War I grew - border controls, which generally never went away after the end the war.
Patsy Baudoin's review of The Passport: The History of Man's Most Travelled Document by Martin Lloyd in The American Archivist gives us an excellent summary of what happens next:
Following World War I, however, in an anxious and unsettled era, it becomes much clearer that cooperation among nations, at least at the administrative level, was necessary for a passport system to work effectively and efficiently. In 1920, the League of Nations' Provisional Committee on Communications and Transit convened an International Conference on Passports, Customs Formalities and Through Tickets precisely to resume controlled travel and set the world back on a course of economic recovery. A far-reaching resolution emerged from this conference: signatories "should agree on a uniform style of passport issued to identical standards".
By July 1921, the fully redesigned passports with detailed specifications on size and content replaced the existing documents.
Here's the micro-history of the passport published by the Guardian.
Tangentially-related histories include the problems created with this system, which is that travelers now has to have a passport and be a citizen of a country. This is especially problematic for the growing number of stateless individuals persecuted and ousted from their homes - specifically Russian refugees following the country's civil war. This lead to the appointment of Norwegian explorer and statesmen Fridtjof Nansen as the League's High Commissioner for Refugees in order to deal with the growing crisis and his development of the "Nansen Passport" to be issued to the stateless. It was later used for Armenian and Turkish refugees as well. One of the real success stories for the League of Nations in my book. Here's a quick write up on Nansen from the UNHCR.
As for your questions about citizenship (which is going to be more complicated), the intersection of that, passports, and nationalism is when you'll have to turn to the ever ubiquitous Imagined Communities by Benedict Anderson. Probably the most necessary read for a foundational knowledge on these topics, and I believe it should answer at least a few aspects of your additional queries.
One of the earliest recorded uses of travel papers comes from the Christian bible, in which an anecdote from about 450 BC is written. In this anecdote, Nehemiah requests papers for travel from modern-day Iraq to modern-day Israel. Nehemiah 2:7-9 reads:
I also said to him, “If it pleases the king, may I have letters to the governors of Trans-Euphrates, so that they will provide me safe-conduct until I arrive in Judah? And may I have a letter to Asaph, keeper of the royal park, so he will give me timber to make beams for the gates of the citadel by the temple and for the city wall and for the residence I will occupy?” And because the gracious hand of my God was on me, the king granted my requests. So I went to the governors of Trans-Euphrates and gave them the king’s letters. The king had also sent army officers and cavalry with me.
However, it's widely accepted that, in the early 15th century, King Henry V invented the first standardized travel document, which was more akin to what we know today as a passport (although, the word "passport" didn't appear with any regularity until about 100 years later). These were essentially letters from the king (later the Privy Council) stating that the bearer had the king's diplomatic backing and was to be treated well. If you look in some modern passports, you'll see similar codified language. In the passport I happen to have sitting on my desk, some text near the front reads:
The Secretary of State of the United States of America hereby requests all whom it may concern to permit the citizen/national of the United States named herein to pass without delay or hindrance and in case of need to give all lawful aid and protection.
As you can see, the protection of a person abroad by their home government has survived the past 600 years.
In the 20th century, passports became standardized and used everywhere. This started with a League of Nations meeting that performed the standardization. World War I saw many countries enforce passport requirements for travel, and then by the 1980s, passports started using standardized type and other features that made them instantly recognizable and usable by any immigration authority around the world.