Scattered across multiple planes, always in watery areas. There are fragments on the Elemental Plane of Water; the first layer of Mount Celestia (I think that's the layer with the holy ocean, not positive); Dagon's realm in the Abyss; under the Styx in Hades; etc.
The highest mountain in Atlantis had a temple at its summit, and that is the only part which remains on the Material Plane (albeit at the bottom of the ocean). It has sealed portals connecting to the other fragments.
When Atlantis sank, it was meant to be plunged entirely into Dagon's realm, forming a vast permanent portal through which the demon prince's spawn could overrun the mortal world. The kingdom was shattered in a last-ditch countermeasure by the Atlantean priests and wizards, scattering its fragments across the multiverse and turning one giant portal into lots of little ones that could be sealed.
Now a group of priests are seeking to reunite broken Atlantis, and might recruit the PCs to help. What the priests don't mention is that if they succeed, Atlantis will reunite in the Abyss, and Dagon's scheme will come to fruition at last. (The priests themselves are mostly unaware of this; they have been duped by a cell of Dagon cultists high up in their order's ranks.)