SRAM based FPGAs have a non-volitile source for their configuration data. Typically this is an external serial ROM (the simplest, but most expesive), or a microcontroller with some sort of PROM. One can also program through a channel like a PCI bus.
There are other FPGA technologies that are non-volitile, though they're several generations behind the technology curve. SRAM based FPGAs are usually done on the same processes as microprocessors and have the advantage of that performance.
As above, one puts a "boot PROM" in the circuit. There are many was to do this.
Yes, though they're not the fastest nor densest parts. They're alos a PITA to use.
Generally, yes. It's not a big deal though. The FPGA manufacturers build several method of doing this into their devices. Depending on the design constraints, one is less painfull than the others. ;-)
Google "logic jump station". Also look at the Xilinx and Altera sites. There is a *ton* of information there.