I read that a blackhole has an entropy that is given by the area of its event horizon (measured in Planck units). Does that mean that this information is actually physically stored there? If yes, how can that be since there may be nothing there at all (no electrons for example that could carry this information in terms of spin up or spin down)? Is it perhaps stored in the vacuum somehow ?
Ultimately this is a highly theoretical question, and while appropriate here you may find perusing the Physics site helpful to get deeper answers.
But here's the basic idea for how I think about this. It's based on asking "where else would the information be?"
Imagine the universe is a 2-dimensional sheet. A piece of paper, say. And that's all there is for things inside this universe: no desk it's sitting on, no air around it, etc. Whatever inhabitants of this universe wish to talk about must be contained within this 2-dimensional sheet of paper. Now imagine there is a hole in this paper. What can in-universe inhabitants possibly use to learn about this hole and whatever properties it might have? What to us, as outside observers is "the hole" is inaccessible to them: it's not part of the paper (it's an absence of paper). But the border of that hole is accessible to them. So whatever information this hole conveys to this universe must be accessible through that border, and the border only: anything else either doesn't exist, or is some distance away.
The hole in this paper is our analogue for the black hole in our universe. "The inside" of a black hole doesn't make sense to an external observer, because the universe—the sheet of paper— ends at the border of the hole. There literally is no inside to speak of.
The analogy gets complicated a bit by the fact that if you are not an external observer, but are infalling, then you can in fact pass through what the external observer calls the border. There's the whole information paradox as well when we bring in quantum mechanics. But this is the basic gist of things: the black hole is a topological/geometric defect (as general relativity is a theory about the geometry and topology of space), and the only "part" of it which is contained in our universe is its border, the event horizon.
The actual physics at and near the event horizon is still a matter of significant debate and research. This little exercise does not explain why the information of the No-hair theorem is accessible, but nothing else is, for example. It just offers some intuition about why whatever information is accessible must, in some sense, be stored "on" the event horizon. As far as external observers are concerned, that's the only place it ever could be!
Mark Van Raamsdonk in his Lecture on Gravity and Entanglement (https://arxiv.org/abs/1609.00026) provides the following answer to the question: He states that the statistical interpretation of black hole entropy remained mysterious for decades since there did not exists a framework to understand the microstates of black holes. However, according to him, our understanding of the microstates of a black holes has dramatically changed with the discovery of AdS/CFT (Anti-de-Sitter/Conformal Field Theory) correspondence  put forward by Juan Maldacena. The basic idea here is that certain non-gravitational quantum systems (CFTs), defined on fixed spacetimes on a sphere, are equivalent to quantum gravitational theories whose states correspond to different spacetimes with specific asymptotic behavior.Each state as well as observable in the non-gravitational system corresponds to a state and observable in the dual gravitational theory and vice versa.
In this context, he explains, that a Black hole in Anti-de-Sitter space is identified with a high energy state in the corresponding CFT. Such a theory has a discrete spectrum |E_i> and a the thermal state corresponds to the usual canonical ensemble. Hence the entropy of the black hole is identified with the counting of microstates of this CFT.
 Anti-deSitter is a space with constant negative curvature