How does a normal map contain more information than a heigh map? I know that a bump map stores height information as 1D grayscale values, while normal maps store normal information as 3D color values.
However, a normal map can be obtained from the spacial derivatives of the bump map, what can even be done in standard image manipulation softwares, like Gimp.
So, I would conclude that the normal map does not really stores more information, it simply stores it in a &quot;fancy&quot; processed way. Both maps would be just different standards for representing the same thing and there should be no reason for both bump and normal maps exist. We could chose only one by convention.
However, both bump and normal maps are commonly used, even together sometimes. They are both implemented in Blender and other 3D softwares.
So I suppose I must be wrong in some way, and both maps actually achieve different things. But I can't figure out what I'm missing
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.