If Max Tegmark is using the words "self-aware substructure of the universe", then he is referring to agency and the beings who possess it, for example us. If the universe is perceived as a mathematical structure, than not all of the structure possess the capacity for perception, hence the delineation of a sub-structure which by definition means a smaller portion of the structure.
Is he using structure to describe physical reality the same way he is to describe, say a non-Abelian group? Yes. Does it make sense? To some extent yes. Imagine being lost in your head and thinking that all of your thoughts are information, and that all of the things your thoughts reflect can be thought of as information, for instance particles are described as mathematical waves, or atoms can be described with bits, then it might be easy to just declare the universe itself mathematical instead of separating the universe into an external, concrete reality made of matter, and an internal, abstract structure made of logical, arithmetic, and set theoretic structure. Many bright people think along these lines.
Of course, those of us who are realists of various flavors think this thinking is silly. Rocks may be made up atoms, but our thoughts which follow from the computational functionality of the neurons in our head are not the same as the rocks we think about. This is a theme that Platonic roots where numbers are instantiations of Forms. A famous example of this thinking is also encompassed by an essay called The Unreasonable Effectiveness of Mathematics.
There are plenty of arguments against a Platonic view of the universe, but alas, you didn't ask about them. ;) But do consider this. Note all messages require a medium. If you deny this, identify a message without a physical medium. Now, if all messages, or all information requires a physical embodiment, be it electrons in a flip-flop or clay or paper and ink, then the question stands, what is the mathematical structure of the universe expressed in? What is the medium that encodes the information that represents physical reality? If you are unable to provide scientific proof that this medium exists, then you must reject the notion that the universe is made of information until you can meet empirical requirements. If you reject the need for empirical requirements, then you are participating in pure rationality and Metaphysics with a capital M, which by scientific thinkers is generally labeled as meaningless. So, you find yourself having to choose between science or the position that the universe is made of information.
Now ask yourself, are you willing to bet against science? If you are, then you might consider argument by defenestration, and prove us realists wrong and throw yourself out a window to prove us wrong. I would advise against it, of course.
EDIT 2019-08-26: In response to the fair critique that the argument against Tegmark's claim is circular, first, remember that Tegmark is the original claimant, and as such, the burden of proof to show that the universe is a mathematical structure would be his to show that the universe is a mathematical structure (presumably represented in some sort of math machine). Obviously, his actual argument isn't present here, so I've outlined a sketch of an objection.
Is the argument circular, as suggested? As a skeptic and empiricist, in a way, yes, I have rejected the notion that the universe isn't a Platonic realm as an assumption, and hold that the burden of proof is to show that it is. Perhaps Tegmark has an explanation of how everything being a mathematical structure allows me to have sensory input to discriminate the material from the non-material, presumably as some sort of simulation. So, yes my manner of justification presumes some elements of my conclusion, but that's ultimately because rationality has limits, and it is those limits that show that a purely rational answer cannot be the solution, and that we must appeal to our physical embodiment as a method of discriminating what is, and what is not. See my response in the post regarding the Muenchhausen Trilemma