TI PAL datasheet says that they use titanium-tungsten fuses. Don't know what AMD used, but I guess it's something similar. Aparently they don't seem to be very reliable as they get old....
From AMD's datasheet for the PALCE16V8 family:
- Pin and function compatible with all 20-pin GAL devices
- Electrically erasable CMOS technology provides reconfigurable logic and full testability
The PALCE16V8 is an advanced PAL device built with
low-power, high-speed, electrically-erasable CMOS
technology. It is functionally compatible with all 20-pin
GAL devices. The macrocells provide a universal device
architecture. The PALCE16V8 will directly replace the
PAL16R8 and PAL10H8 series devices, with the excep-
tion of the PAL16C1.