When becoming a resident of Munich, or indeed anywhere in Germany, you must register your address with the authorities within 7 days of arrival. In German this is called: Anmeldung
When leaving you have to deregister again. In German: Abmeldung
In Munich the registering and de-registering is taken care of at the Kreisverwaltungsreferat, or KVR for short, at Poccistraße. If you live outside of Munich city limits (Stadt München), then you'll want the town hall for your town. You need to get your non-tourist visa first.
Change of address / Ummeldung
To register a change of address you don't need to go to the KVR in person. Instead you can download the form off the web and send it in by post. The forms for Ummeldung and Anmeldung are one and the same. It is available online here: muenchen.de / Anmeldung (PDF file) or English version: here
The completed form should be sent by post to:
Landeshauptstadt München
Kreisverwaltungsreferat
Hauptabteilung II - Einwohnerwesen
Bürgerbüro
80466 München
Note that they don't accept it by e-mail because they need your signature on the document. Oh roll on the days of electronic signatures!
Deregistration / Abmeldung
you just go to the residence bureau (Einwohnermeldeamt) and say you need to pick up a form to deregister (Abmeldung). they fill it out that is it. not very painful.
you can usually downnload those type of forms on muenchen.de and fax them in
Details (in German) are here:
Notes
Make sure you leave the box for "Religion" blank unless you want to pay church tax (usually something like 3 to 9% of your income).
The information submitted in a registration is shared with numerous other parties such as political parties and the GEZ (the TV license people). If you want to prevent this sharing of information (important for tin-foil hat wearers) then you should also submit this form: Uebermittlingsperre.pdf