Where is the information stored?

[Alex K]

so the surface is akin to an algorithm describing the volume? This gives me the sense that string theory should be replaced with bubble theory.

I wouldn't put it in those words - let's say you can formulate an "algorithm" (a theory) using only two coordinates of target space, and a third dimension arises kind of as an emergent thing.

In a conjectural realization of this principle, the AdS/CFT correspondence, the reduced-dimension picture is still a string theory (or in the more conservative version, a field theory), where the strings are more or less localized on a surface brane.