Die Freizügigkeit der Arbeitnehmer gehört zu den vier Grundfreiheiten, welche durch das Gemeinschaftsrecht garantiert werden (Artikel 39 des EG-Vertrages) und ist somit auch wesentlicher Bestandteil der europäischen Bürgerrechte. Die Gemeinschaftsregeln zur Freizügigkeit der Arbeitnehmer gelten auch für die Mitgliedstaaten des Europäischen Wirtschaftsraumes (z.B. Island, Liechtenstein und Norwegen).
Die EU-Erweiterung zum 1. Mai 2004 um acht mittel- und osteuropäische Länder (Estland, Lettland, Litauen, Polen, Slowakei, Slowenien, Tschechische Republik, Ungarn) und zwei Mittelmeerinseln (Malta und Zypern) war die größte und ehrgeizigste Erweiterung in der Geschichte der EU. Nur die Staatsangehörigen von Zypern und Malta haben die volle Freizügigkeit, d.h. den uneingeschränkten Zugang zum deutschen Arbeitsmarkt erhalten. Für die übrigen EU-Staaten gelten Übergangsfristen, bis zum 30.04.2006 (Regelungen kann Deutschland erst um drei Jahre, danach noch einmal um zwei Jahre verlängern („2-3-2“-Regelung). Arbeitnehmer aus den osteuropäischen Beitrittsstaaten dürfen bislang nur mit einer Arbeitserlaubnis in Deutschland tätig werden.

Du musst dich "nur" regulär ummelden, dich bei der zuständigen Ausländerbehörde am neuen Wohnort melden, die dir dann eine Aufenthaltsgenehmigung / Freizügigkeitsbescheinigung erteilt. Ist in jedem EU-Land mehr oder weniger gleich geregelt. Schweiz ist nicht EU, da gelten andere Regelungen, die unterscheiden zwischen Arbeits- und Aufenthaltsgenehmigung, sowie der Staatsbürgerschaft...