As a US citizen you can apply directly for the residence and work permit at the Ausländerbehörde.
Once you have the Wohnunggeberbescheinigung (§19(3)) apply for an online appointment to register.
Once you have moved in, you must register within 2 weeks (§ 17(1)).
With the appointment you fulfill the reporting conditions , since the waiting time is horrendous (up to 4-6 weeks).
Also, do I need to be registered at a residence (Anmeldung) before I apply for the visa?
If you already moved in, yes
- at least the date of the appointment application
One criteria for issuing a residence permit is whether the applicant will obey the law
- not doing so would give a bad impression
Federal Act on Registration of 3 May 2013
Chapter 3
General registration requirements
Section 17
Registration, deregistration
1) Anyone who moves into a residence shall register with the registration authorities within two weeks of moving in.
...
Section 19
Cooperation by the supplier of the residence
(1) The person supplying the residence shall be obligated to cooperate with registration. The person supplying the residence or someone authorized by him or her shall confirm in writing or pursuant to subsection 4 electronically within the period given in Section 17 (1) that the person required to register has moved in. He or she may contact the registration authority to find out whether the person required to register has done so. The person required to register shall provide the person supplying the residence with the information necessary to confirm that the former has moved in. Confirmation pursuant to the second sentence may be provided only by the person supplying the residence or someone authorized by him or her.
...
(3) The confirmation of the person supplying the residence shall contain the following data:
- name and address of the person supplying the residence and name of the owner, if different,
- date moved in,
- address of the residence, and
- names of the persons required to register pursuant to Section 17 (1).
...
Sources: