There isn't any actual "swapping" of code running in the C64's main memory. Rather, it is an instantaneous switch in whether the code is running from the main memory of from the cartridge memory. Furthermore, with a more sophisticated cartridge like the C64 Ultimate II, we also switch between running native code on the 6502 and running embedded code on the cartridge's own embedded CPU.
The Ultimate II cartridge works under the same principle as the older "Freezer" cartridges that have been popular on the C64 since 1985 (I believe ISEPIC was the first). Specifically, it takes advantage of the "Ultimax" mode that a C64 cartridge can enter. This mode was present in the C64 so that it could be compatible with cartridges designed for Commodore's MAX Machine.
When in Ultimax mode, the cartridge can take over the area of the C64 memory map usually occupied by the Kernal ROM ($E000-$FFFF). This means the cartridge takes over all the interrupt handlers too ($FFFA-$FFFF). Additionally, the cartridge is able to halt the 6502 in the C64, and master the bus (using the cartidge port DMA line), including the I/O device region of the C64 memory ($D000-$DFFF). In other words, full cartridge control of execution, memory, and I/O!
The code for the Ultimate II is open source. For more information take a look at
c64.cc. This is the main part of the Ultimate II's application. It is written in C++, and compiled to run on an embedded processor that is synthesized in the cartridge's FPGA. Specifically, the methods
C64::unfreeze are good starting points to understand what is going on. Once you understand that this C++ code running on the cartridge co-processor can reach into the C64 memory and IO space, then it is easier to imagine how it can do things like display the menus, DMA load software directly to the C64's RAM, emulate many older C64 cartridges, and do it all without disturbing the internal state of a "frozen" C64 program.