If the virtual address space can be larger than the physical address space, how are the address mappings stored in memory?
The trick to making this work is "paging."  When bringing data from a hard disk into physical memory, you don't just bring a few bytes.  You bring an entire page.  4k bytes is a very common page size.

If you only need to keep track of pages, not each individual byte, the mapping becomes much cheaper.  If you have a 48 bit address space and 4096 byte pages, you only need to track which of the 2^36 pages (roughly 69 billion pages).  That's much easier!  The record of where all of the pages are found is known as a "page table."

If you actually need 1-256 TiB of memory, then giving up a few gigabytes to store this page table isn't a big deal.  In practice however, we'll do things like use multi-level page tables, which lets us be a bit more efficient, keeping pages only for regions of the address space that we are actually using.