How does a normal map contain more information than a heigh map?
The maps do not achieve different things; they both turn into normals to be read by the shader or raytracer.  But you're not wrong: you can make a typical tangent space normal map from a bump map and a UV-mapped mesh*, but you can't make a bump map from a tangent space normal map**.  If anybody is saying that a normal map contains more information than a bump map, they're mistaken.
But there's a difference between having more information and having more precision.  And when talking about typical formats-- 8 bit per channel, RGB(A) images-- a normal map has more precision than a bump map, because it uses more channels to store that information.  The normal map is using 16 bits per texel to store its normal.  (Alpha is unused, and one of the color channels is redundant.  Well, almost redundant.)  The bump map is only using 8 bits per texel.
There is one, tiny way in which a normal map contains more information than a bump map, but it's not a way that anybody cares about: a normal map can actually flip the normals, by using a blue channel less than 0.5.  Of course, nobody ever does that.  If they did, it would be more appropriate to say that the normal map uses 17 bits per texel to store its normal (because then, the redundant channel's sign, less than or greater than 0.5, matters.)
What would happen if you were using 16 bpc images?  The difference in precision between the normal map and the bump map would no longer be noticeable.  Does that mean that a bump map would be indistinguishable from a normal map?  No, you could distinguish them, because of the different ways that they interact with texture lookups and filtering.
*You can make an object space normal map from just a bump and a mesh.  But PS is assuming a default plane mesh-- you can't make a normal map of any kind without a mesh.
**You can approximate it.