So in the game setting where do Android Souls come from, and what state are they in when the enter the shell body? Or if they come as adults? How?
All souls in Pathfinder originate from energy flowing from the Positive Energy Plane through portals in the suns to take up residence in newly conceived bodies. The android article from the Iron Gods AP had androids automatically and unwillingly entering renewal every 60-80(?) or so years, after which they "died," that soul went to get judged, and a new soul took over the body as it was still physically functional and missing one, therefore open to a new one.
Some things have changed for Androids in Starfinder, but maybe not that.
In addition to that, souls who don't fit in any of the afterlifes get reincarnated. It's not clear how common this is.
Currently the starfinder rulebook says that it is voluntary to "die" as an Android so a new soul can come. I was also wondering if a soul from one person could end up in an Android shell.
In addition to that, souls who don't fit in any of the afterlifes get reincarnated. It's not clear how common this is.
Its kind of generally implied that anytime someone passes on, and has a God that they worship, they go to the afterlife of that god. Beyond that comes their deeds, intents, and actions determining their afterlife (basically, their alignment).
Of course while its not written, I get the distinct sense that how it works from there is that in general, while the ones with a god get fast tracked into a higher Outsider; the more "agnostic" among the petitioners typically end up having to choose to be where they are (perhaps the evil planes excepting), as often in cases such as the LN petitioners, they have to "do" something before they're able to ascend.
I'm guessing that reincarnation probably only happens for the few who get to that point and decide to turn back... Or I guess earlier if Pharasma judges someone to not have had enough time to choose their fate; such as in the case of children.
I'm not sure there's really that many cases of someone who doesn't have a suitable afterlife to go to. The exceptions may be True Neutral Druids, but even they could go to Nirvana. Also True Neutral in general ends up being a pretty terrible afterlife to go to, and aside from Pharasma worshipers, I don't think anyone is going to go for that. (Especially if it results in becoming an Aeon.)
In any case, I'm erring on the side of suggesting that "Not Many" people are naturally reincarnated; unless they basically devote their life to it.
In (AP #85) Iron Gods, part 1: Fires of Creation:
...with age and the inevitable failing of their systems weighing upon them, some androids proved able to bring on a reset of their own initiative and passed this knowledge to others of their kind. This process, now called renewal, erases the android’s mind, releases its soul to travel to the Boneyard, and leaves its body a vacant shell. For 2 to 3 weeks, the android is inactive as nanites rebuild and restore its body to its original, youthful state. Ready to live again, the android awakens to a new life with a reborn soul and, occasionally, faint residual memories of its prior lives.
Traditionally, an android’s renewal was accomplished in a technological “coffin” reminiscent of the incubators that give androids life. On Golarion, cradles built in the image of these sarcophagi have replaced the original chambers, and continue to provide privacy and safety during the transcendent journey of renewal. Despite these elaborate constructs, renewal requires no special vessel, merely time and protection....
How much of this is still true and how much has changed in Starfinder has yet to be revealed. It seems possible that androids' minds come with a standard "Androids 101" block of knowledge ("wiki"?) likely encoded in firmware somewhere in their bodies. As for the rest? Who knows.
Perhaps when the soul is freed/uploaded to the afterlife, some mechanism downloads/needlecasts a new personality, or an amalgam of random personality components, from the Akashic Record? While the body is being rebuilt by nanites for the next occupant, mnemnites are restructuring the brain hardware/cortical stack and encoding it with the new memory and personality, so that everything is ready when the new soul arrives.