Genetic information storage and the extent to which it controls appearance/structure
The common phrase I've heard is "DNA isn't a blueprint, it's a recipe". More specifically, the nucleotides in DNA correspond to which proteins get made (coding DNA) and when and where (regulatory DNA). Just like a recipe doesn't specify the exact color of a cake or the position of each raisin, but does say "cook the cake for this long" (which will, in interaction with the heat of the oven, determine its color) or "put in this many raisins, at this general point in this general area", DNA doesn't contain the exact information of how you end up looking (hence why identical twins aren't really identical), but it does say how to make you how you are.

It also illustrates how much has to be "programmed" initially; how we are really needs to be understood as an interaction between DNA and the environment through the process of development, just as you can't completely understand a cake just from the recipe, you also need to know how chemistry and physics cause the things in the recipe to have the effects that they do. A lot of what goes on in development is cells growing, changing or dying depending on the chemical environment they're in, which includes what their neighboring cells are. The information in DNA basically consists of affecting that via what proteins get made when and where during development.

As for whether complete information about the entire organism's structure is stored all over the body, yes and no (but mostly yes). Yes, by default every cell in your body inherited its whole genome from the original zygote that started things, and you can indeed in theory clone a whole person from many random cells in the body. However in practice it depends on the cell: some cells lose their nucleus entirely, like red blood cells, so of course they don't contain the body's whole genome. Other cells could theoretically multiply or eliminate certain genes in a similar way as they specialize for the specific task they need to do, meaning they won't end up with the same genes as all the other cells in the body, but this isn't thought to be a common phenomenon especially in humans (cells will vary more in the expression pattern of their genes without necessarily changing the DNA sequence itself). This is also ignoring the ordinary mutation rates in DNA as the cell divides, which will yield differences between different cells of a given body even without that being a deliberate process. Hence cancer !

Some references on the possible variations of DNA in somatic cells (i.e. not ova or sperm)

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3497787/


  It is commonly assumed that all healthy cells that arise from the same zygote possess the same genomic content, with a few known exceptions in the immune system and germ line. However, a growing body of evidence shows that genomic variation exists between differentiated tissues.


Elimination of actual DNA in nematodes and lampreys :  

https://www.ncbi.nlm.nih.gov/pubmed/23123092  

https://academic.oup.com/mbe/article-abstract/33/9/2337/2579241/Characterization-of-Somatically-Eliminated-Genes?redirectedFrom=fulltext

Quote from the first abstract:


  Chromatin diminution is the programmed elimination of specific DNA sequences during development. It occurs in diverse species, but the function(s) of diminution and the specificity of sequence loss remain largely unknown.


I have found no mention of it happening in humans however.