Holography is magical indeed! But some of the popular tropes people repeat about it are misleading, which adds to the air of mystery. Here is my feeble attempt at demystification:

A proper full parallax, full color hologram is probably not a strictly 2D surface - information is encoded volumetrically, in the thickness of the medium. Some types of holograms are indeed strictly 2D ("surface holograms"), but those tend to have stricter replay restrictions involving some combination of single parallax, only working for one wavelength, or being extremely picky about the illumination angle. The issue is that many combinations of wavelength and incidence angle produce the same interference pattern on a 2D surface, so you need to constrain it somehow. This is why the holograms you see on credit cards etc are rainbowy - they really are a 2D surface, just stamped foil.

Regarding the good kind of hologram ("volume hologram"), it does not exactly encode a "3D" scene - it encodes a slice through the lightfield, recorded at its surface. Technically this is 4D - 2 dimensions for the intersection point of a light ray to the plate, and 2 more to describe the direction it's going in. It doesn't "know about" the actual structure of the scene, and there's not really any kind of spooky "the whole is contained in every part" thing going on - look through a part of the hologram, and you get the light rays that go through that part. There's nothing especially mysterious about being able to see the "whole scene" through a part of hologram, any more than it's mysterious that you can still see faraway objects through your window even with the curtains half drawn. In the limit case, you could mask off everything except a tiny pinhole on the plate, and if you could somehow place your eye against that pinhole without your head blocking the illumination you would see only the light rays that pass "through" that hole: in other words, a 2D photograph taken from that spot (you have masked off 2 of the 4 dimensions).

So how can a pinhole-sized spot on a plate somehow reflect different amounts of light across different angles, to make a whole picture? Tiny mirrors, basically. It's like if you took a disco ball, put color filters on each facet so the dots on the wall made a picture, and then figured out a way to shrink it down so far that the mirrors overlapped. How do you overlap mirrors? You make them out of a few dozen parallel partially reflective surfaces, instead of one fully reflective one ("Bragg mirrors"). This has the added bonus that you can also control the color: the spacing of the parallel mirrors causes a particular wavelength of light to constructively interfere, the same way a soap bubble or an oil slick does (the outer and inner surface of the bubble/slick both reflect light, and the colors shift because the thickness is constantly changing). The thickness of the hologram is important because it allows space to "aim" the mirrors. The thinner the hologram, the fewer stacked partial mirrors will fit, and the less precisely it can select wavelengths or aim the light.

The way I see it, the real magic of holography isn't so much that such an object is possible - the physics is fairly intuitive once you understand the pieces, and the math mostly boils down to trigonometry. No, the magic is that you can record them - you can create this complicated assembly of overlapping nanotech micromirrors merely by reflecting an expanded laser beam off something, taking care that it goes through the plate first, and mathematical symmetry takes care of everything. The clean beam going through the plate is symmetrical to the replay light, and the reflection is symmetrical to the replayed scene. Reference beam + object beam = interference, and so reference beam - interference = object beam. It is an extremely neat trick.