여권과 집 계약서를 들고 가셔야 하구요.
시청에 전화를 하셔서 물어보세요. 대부분은 시청에서 할 수 있으니까요.

kanon 님, 안녕하세요.
답변 달아주셔서 감사합니다. 그런데, 제가 찾은 정보랑 다른 점이 있어서 내용을 덧붙입니다.
다른 분들도 참조하는 글이기에 보다 정확한 정보를 알리고자 함이니 오해하지 않으시길 바랍니다. ^^
이하는 kultur 님이 덧글로 적으신 글입니다.

==========================================================

거주자등록은 외국인청이 아닌 가까운 Bezirksamt에 있는 Buergeramt에서 합니다. 꼭 본인이 사는 곳이 아니어도 베를린시내의 아무 Bezirksamt에서 하면 됩니다.

거주등록에는 보험가입여부가 필요치 않습니다. 안멜둥용지에 본인과 가족사항 주소 이사날짜 등 내용을 기재한 후 아래에 집주인 주소와 이름 그리고 본인이 사인하고 신청하면 됩니다.

의료보험여부는 비자를 신청할 때 첨부해야합니다.
그러므로 보험가입과 거주자 등록은 순서가 중요하지 않으며 다만 비자받을 때는 이 두가지가
이미 갖추어져 있어야 합니다.

보험은 어학원에서 할 경우는 잘 모르겠지만 일반적으로 정식 학생이 되기전에 드는 사보험들은 인터넷으로 가입한다면 가입과 동시에 가입증명서를 프린트할 수 있습니다. 물론 비자받을 때도 인정되구요. 그러므로 어학원을 통할 경우에도 그리 시간이 걸리지 않을 것 같군요.

=========================================================

kanon님 제가 착각한 부분이 있네요. 전 Rathaus는 베를린 전체의 시청만 말하는 줄 알았는데 한국으로 치면 구청에 해당하는 Regierungsbezirk도 Rathaus라고 하더군요. ^^
답변해 주시면 감사합니다.