But in order to be compressed, don't we have to load the image into memory first, uncompressed? I don't quite see how this could result in reduced memory usage.

It needs to be decompressed, but it does not stay uncompressed. That memory is only used temporarily. Games usually have a pinned staging buffer to upload data to the GPU. This memory is reused and does not contribute significantly to the total memory use.