Disclaimers: my answer will be more English than anything else as that is my main area. But it's a popular area for the large English-speaking audience out there because we all descend from it, so I presume that's fine. Secondly, I'll be leaning more into the early Early Modern period, but the 16th century is similar to the Late Medieval and I'll try to incorporate some specifically Medieval elements.

Firstly, as far as I know there where no specific restrictions on permission to migrate to the city. It's harder to prove a negative but people seem to come in a pretty free manner in urban migration and I've seen no references to permission to come into London or anywhere else (I have seen passports for Ireland and building restrictions on expanding the city). During times of plague there might be some form of restriction perhaps.

On whether they had already arranged work, I believe it would be a mixture of the two. Social connections by friends and family were really important in pre-industrial society, so if they had a contact in the city they might have a pre-arrangement or at least a specific idea of where to go looking. Others might come with a specific industry in mind. "Medieval People in Town and Country: New Perspectives from Demography and Bioarchaeology" by Maryanne Kowaleski (2014) and "Migration in Preindustrial Germany" by Steve Hochstadt (1983) both identify young, not well-off people as frequent urban migrants, and Kowaleski says specifically women most of all. She identifies domestic work in the many employing households and venues that required servants as a big part of all these young women and the male counterpart would be labourers' apprenticeships. Plenty of urban opportunity in those fields. It is also the case that people sometimes came to the city to beg, or try their hand at any employment they could get. In the Sixteenth Century during war with Spain, London picked up an increase in beggars and homeless job seekers because of the strained economy. The other part of this movement is outmigration though, mentioned by Hochstadt. Many people left for country residences or back to their villages, when they wanted a break from city conditions or changed their minds about moving. And a significant portion of the many young migrants were looking for temporary work. Craftsmen might travel doing different jobs, as builders, masons and other people involved in architecture did (mentioned in "Wages and Earnings in Late Medieval England: Evidence from the Enforcement of the Labour Laws" by Simon A. C. Penn and Christopher Dyer (1990)).

As Kowaleski says there were valid reasons for city migration, including a less seasonal food supply, and one of those reasons was the job market. While the city could never take as many people as came looking for work because there was so much competition, if one wasn't well off in the country area you came from it was certainly easier to find novel opportunities in the diverse and dynamic market of the cities, rather than the largely familial economy of villages. Shelter was usually easier to find than employment as they were more unemployed people with some kind of residence than people with a job without anywhere to go. But if you were unemployed you would probably end up in a multi-resident building of some sort; perhaps a tenement or an inn, or if you were really poor you could find help with a monastic institution (replaced in the 16th century with secular almshouses and workhouses). The easiest solution would be stay with a friend or relative, which is where having that friend or relative in mind mentioned earlier has additional benefits.

In regards to building your own, building was not cheap and you had to get the rights or rent to a piece of land. Also, there might be restrictions in place in a city against expanding it with more buildings as there was in late 16th century London. If you were to build your own, clay "mudwall" material with a thatched roof and a floor of stones strewn on the existing earth would probably be the cheapest option (Christopher Dyer (2008) Building in Earth in Late-Medieval England, Vernacular Architecture), but that was less popular in cities which were mainly brick and wood. A nice house was very expensive because the fashionable design for walls and floors were multi-layered; the walls were covered with plaster and then panelled, and the flooring was similarly plastered and either painted or had it's own third layer of ceramic tiles, also painted (the flooring construction is mentioned in Miranda L. Elston's "A Persuasive Interior: Reconstructing the Whitehall Palace Privy Chamber" (2017).

The easiest place to go would probably be Southwark, which was technically outside the city limits but that is more the better for access. Southwark was where all the smelly stuff like tanners and also where the public entertainment like prostitutes and theatres were. It wasn't a high class area at all, making it cheap and there would probably be ready accommodation of various sorts available, plus the entertainment venues make it somewhat desirable for those who weren't too proper for that sort of fun. Given all the business that was conducted there from fishmongers to bear-baiting, it would also probably be a good area to look for work. Just a word of advice, if a prostitute tempts you to buy them a prune, don't. They were outrageously expensive and that was a major source of income for the brothels, it's a trap. These details about Southwark are cited by Prof. Michael Dobson in this documentary which includes a map of the colourful street names in the area: https://youtu.be/9tzUrtJAZcc (the relevant area is around 22:30).