Originally CPLDs used arrays of PLDs/PLAs which use a wide network of programmable AND-OR gates to implement logic equations with relatively sparse routing resources between logic elements. FPGAs will use a more fine grained element for implementing logic (SRAM LUTs or small clusters of muxes) with denser routing resources.
That distinction is a bit blurred nowadays because Altera has "CPLD" products that are using conventional FPGA architecture equivalent to what was state of the art for FPGAs 25 years ago.
It is mainly an architecture difference. An FPGA is typically made up of many logic blocks that contain a programmable look up table (LUT) connected to a flip flop. There are also various multiplexers (muxes) that route signals around the flip-flop or to other neighboring logic blocks. In this way, you can chain many of these logic blocks together to create your desired circuit.
A CPLD typically has a network of And or Or gates leading to the pins of the device. The outputs of these gates then feed into the complementary gate (Or for And and And for Or) and then most likely into flip flops. You program the device by selectively connecting the pins through a switching matrix to the various elements of the first logic array and then another switching matrix to the various elements of the second logic array. There is also the possibility for a third switching matrix for feedback through the system.
As the others have pointed out the technical details, the high level difference is that FPGA's are typically volatile and hence lose their programing once there is a power loss. CPLD's have non-volatile memory that allow for hard reseting and so are used in environments that need fault tolerance (factories, airplanes, etc.).
That distinction is a bit blurred nowadays because Altera has "CPLD" products that are using conventional FPGA architecture equivalent to what was state of the art for FPGAs 25 years ago.