They are a new creation by Gond himself, sent to his clerics along with their other divine magic.
They indeed have souls, and these are the souls of followers of gond.
Gond has finally revealed a way he can have constructs that live. He had something along those lines once before: He had build enforcers for Cyric the Mad before Kelemvor took the title of Lord of the Dead, and after showing that technology can stand up to magic, he had taken them back. These enforcers were powered by the souls of some faithless.
After he took them back, Gond improved on the design. He did away with the complete magic immunity (due to an agreement with Mystra), and in 1374, the design was finished.
You see, You can let someone stay dead, you can raise/resurrect him, you can reincarnate him. Or you can Incarnate them: The mechanical bodies are first constructed by Gond's Techsmiths (often a long time in advance), and when a follower dies, they cast the Incarnate spell (Disciple of Gond 4). The soul returns to the realm of the living (just like with raise/resurrect or reincarnate), but instead of returning to the old body (or a magically created copy of that body, with true res) or into a new, random body, they return to the constructed body. They have their old ability scores (minus the old racial mods and plus the new ones), since the bodies will be created more or less in the image of the person intended to use it.
The whole thing isn't cheap, but the church of Gond sponsors the creation of artificial bodies for Gondsmen who cannot afford it (since Gond wants his technology to be more prominent).
