Hormones. Cells can release information to their surroundings by releasing different chemicals; then cells can measure what other cells are nearby and what conditions they're in. There are special hormones that stick on the cell surface so a cell can measure it's direct contacts. How cells work together to make a body is as miraculous as polyps working together, so I'll talk about that first.

A simple example is the slime mold. It lives as a bunch of individual cells in the soil, and when they run out of food, they come together to make a fruiting body to make the next generation of spores. It's a pretty simple body plan, just a bump with a flower on top, but they make a good example because some of the time they're individuals and some of the time they're linked, so you can see what they do differently. It's a simple enough system that they do it with one hormone. When they run out of food they make a chemical called cAMP that other cells can measure; each cell is triggered by measuring the overall cAMP levels from lots of nearby cells. Then they move towards each other by moving up the cAMP gradient; the more there is, the closer they are to other cells. When they touch at the cell surface, they bind together into their simple body plan.

The more complex the body plan, the more information and more hormone systems it takes to define it. Cnidarians are weird creatures so I'll skip them for a second and go to the fruit fly which is better studied. The early egg is patterned by hormone gradients. It has a front and a back, a top and a bottom, and you can measure the position of each cell from a few hormones. Then it gets complicated. It starts to fold, driven by cell layers bulging and moving against each other. This defines new areas, since the cells inside a fold are in a different environment than the cells outside, which they can measure by cell surface contacts.

This is how the body plan of higher animals is specified: broadly laid out by hormone gradients, and then fine tuned by cell-cell interactions. It takes many, many linked systems to define a full body plan. For example the nerves in your hand don't start there. Once the arm is made with one system, the nerves flow down the arm along another hormone gradient, until they reach the right cells to synapse with, determined by cell surface interaction of another hormone. All these hormones change the behaviour of the cell, by acting as transcription factors that change how it expresses its genome.

Cnidarians are weird because they are made of polyps, so it blurs the line of what's an individual. There's a perspective that what makes up one animal is what shares a reproductive bottleneck: all the parts that are constrained to work together to reproduce, necessarily propagate one genome, so are regarded as one animal. All the ants in a hive are one big animal with one genome because they all reproduce through the queen; the different types of ant are like different tissues that make up a larger body, and each ant is like a single cell. From that perspective, a Man o'War is one animal, because it reproduces from the medusa and not the polyp. This makes it so subunits always have to cooperate, and evolution will make a system that fits together well. They are tightly integrated, and the polyps that make a colony are all genetically identical. I think of a Man o'War as one animal, just with a strange modular body plan unlike other animals. It almost certainly uses similar interactions between units as other animals.

So how might a body plan be coded into binding interactions between polyps? The same sort of interactions that make cells into tissues of different shapes. Polyps are tubes, so if they bind end to end, they make tendrils; if one in a hundred takes only one binding partner, tendrils of a certain length. If they bind on the sides, they form a large flat sheet; if they squeeze in slightly more partners than can fit flat, or if they all bulge at one end, they make a sheet that folds into a bubble. A simple body plan like the Man o'War can be specified just by local binding of polyps, a bit of cell movement, and which specialised type they turn into in that environment.

tl;dr the same way cells know what shape of body to make: hormones and transcription factors