Registering in Germany
Everyone must do this. Registering informs the authorities of where you live. When you move, you de-register and then register in your new location. Unless you are entering Germany, you cannot do the latter with having done the former.
Perhaps this seems too strict but I suggest that you read that page that explains why the continental approach to registration fits the situation on mainland Europe.
When must you register?
If you are staying in an hotel or official guesthouse, you will automatically be registered and you need do nothing else. If you are renting or buying your own place or if you are subletting from another person, you must register yourself.
If your stay is less than three nights, then you need not register. If it is longer the you must register within a set time. This time is three months but it is a good idea to do it as soon as possible. I have, in the past entertained house guests for a week of so and not registered them. I guess that I should have done so but I really doubt that my local registration office would have wanted to hear from me about them.
Where must you register?
To register, you must visit the relevant office in your city. This may be called the Einwohneramt, it is in Paderborn but other names are used in other parts of Germany. You can ask any of your local contacts, they are sure to know where they went to register.
In some cities, the registration procedure for foreigners differs from that for Germans. The reason is that, as a foreigner, you must also have a residence permit and you will get this from an office that deals with this. In Ulm, for example, this office also deals with registration for foreigners. That's handy as it means that you do not have to go to two different offices.
How do you register?
Having sorted out where you need to go, you take yourself and a few simple documents along to the relevant office. You will need the following items:
Your apartment rental contract. (Mietevertrag.)
A letter from your employer saying something to the effect that you, Joe Bloggs will be working in Berlin for them for the next year and you are paid DeM10,00 per month.
It's simple really. If you are moving from another part of Germany, you will need to bring your de-registration certificate as well.
You may find that local practice is such that they will not bother reading some of those documents or that they ask for others. These things are run by the Laender rather than by the Federal Government.
If you are also sorting out your papers for a residence permit then you will need other papers for that. They are described on the Aufenhaltserlaubnis page.
EU law says that you may not be made to pay more than would a German for registration. In my experience though, the fee is normally zero anyway.
Registering gets you all kinds of useful stuff. You will be allowed to vote in some elections and you will be allowed to throw your rubbish away. You will also be made to pay the local rubbish taxes too!
Registering is also necessary for getting power, water, phones etc hooked up and correctly billed. While these folks do not demand to see proof of registration, they do all tie their records together once you are signed up. As an example, if you buy a pre-paid mobile phone ticket, you must give an address and, if that it not registered, the pre-paid phone will not work!
The other thing to remember about registering is to de-register when you leave. It's not just the law, it's a good idea. It does stuff like tell the tax man not to demand a return for the time after you have left.
If you forget, the German tax man may feel entitled to pursue you for tax on money earned after you left Germany!