As the zygote divides into an embryo, how does the embryo know which genes it is to turn on or off in which cell?

There are a number of mechanisms and the majority is probably still unknown in detail. Most rely on certain gradient e.g. along developmental axes. One well-studied element is the chromatin state of Hox genes. See for instance:

Howard Y. Chang, et al. Science 326, 1206 (2009), for a relatively easy to understand read on the topic.