Texture objects contain 3 kinds of information. One of these kinds of information is Texture Storage: the actual pixel data stored in the texture. This page describes the many ways to create storage for textures, modify the contents of storage, and otherwise manipulate the storage of a texture object.
There are three kinds of storage for textures: mutable storage, immutable storage, and buffer storage. Only Buffer Textures can use buffer storage, where the texture gets its storage from a Buffer Object. A similarly, buffer textures cannot use mutable or immutable storage. As such, buffer storage is a special case.
The difference between mutable storage and immutable storage is this: immutable storage allocates all of the images for the texture all at once. Every mipmap level, array layers, cubemap face, etc is all allocated with a single call, giving it a specific Image Format. It is called "immutable" because one the storage is allocated, the storage cannot be changed. The texture can be deleted as normal, but the storage cannot be altered. A 256x256 2D texture with 5 mipmap layers that uses the GL_RGBA8 image format will *always* be a 256x256 2D texture with 5 mipmap layers that uses the GL_RGBA8 image format.
Note that what immutable storage refers to is the allocation of the memory, not the contents of that memory. You can upload different pixel data to immutable storage all you want. You simply can't change a 256x256 texture into a 1024x1024 texture the way you can with mutable storage.
In general, if your implementation supports creating textures with immutable storage, you should use it wherever possible. It will save you from innumerable mistakes.