So there is a formal law stating that all citizens need (should, is expected to) have an address. But of course not everybody has an address registered. By choice or other reasons.

If you don't it doesn't mean you get arrested, thrown in jail. It is just a requirement for a lot of things in the public services to work in general. The social services for example are pretty good at handling, solving issues like these when you are homeless.

You can be registered as having no address. In that case there are special procedures for getting mail and so on.

I've heard that they're given the address of the local municipality main office, but I'm not sure how correct that is.

Homeless in Sweden? You'll be given a place to live in.