You're thinking of paletting from a modern perspective. That is, you're thinking of palettes as a part of the image, with each image owning its own palette.
In SNES-style hardware, palettes are global. You don't design your palette for your images, you design your images for your palettes. Well, it's a complex interplay between the two, but the needs of the palette primarily inform the art design of an image.
You don't get to change palettes in the middle of rendering a frame on the SNES. You set the palette at the beginning of the frame and then render everything in the frame with it. If you have a bunch of different sprites, then they need to be designed to share a lot of colors.
No SNES game developer would be so wasteful as to assign each sprite its own individual 8-color palette index (except maybe for the main character). Multiple sprites will use the same palette index. You have different palette indices for variety of sprites, but a lot of sprites are going to have to share. Which means that a palette has to serve the needs of multiple sprites.
The palette gets set by... the game setting the palette. This ain't rocket science.
At some point in time, the artists got together and came up with the available color palette. They probably went through several iterations of palettes, so that they could get the most out of the limited color palette space. They probably got together with the game designers so that they could have sprites that conflict in their palette, simply by forcing the developers not to put conflicting sprites in the same level.
Once all that was nailed down, they just did their work, making each sprite work with the palette colors they worked out Again, this probably involved many iterations.
The tools they used to create those images were not programs like Photoshop. Look around the Super Mario World rom-hacking scene for examples of the kinds of art tools they would use to generate sprites. Those tools are given a palette to work with, and you build your image only from those colors.
The source of the palette was not imaging software; it was designed explicitly by the developers.
For the SNES, image data and palette data live in different places. Images tend to live in large blocks of data in the ROM. Palettes tend to be hard-coded or otherwise live in tables in entirely different places in the ROM. The link between the two is merely a well-educated coincidence.
Take Super Mario World, for example. A sprite is a game construct that is attached to a level. But the images those sprites use depend on certain colors being in certain palette indices. How does that happen? Exactly and only because that level just so happens to put those colors there. That is, each level has a setting for which palettes to use (a palette of palettes). And if the level loads the right palette for the sprites that level uses, then everything appears fine.
This is one way such linkage happens. But individual games can do things a different way. Indeed, even in SMW, there are some palette entries that simply don't change from level to level, and many sprites use colors from them. So many sprites will be unaffected by level-specific palettes.
That's (part of) why you'll notice that many enemies show up in lots of levels, while others only show up in a few.
In any case, the point is that images and their palettes live in different places, and they get to the system in different ways. Games are carefully coded, in terms of level design or whatever, to use sprites when the right palette is available.
