Napster used a centralized server for indexing but downloads were peer-to-peer. This is what made Napster so awesome on college campuses: you could find anything, but if you chose a local peer, the actual download would happen over the college LAN at godly speeds.

Gnutella brought peer-to-peer searches. Basically it used a flood-fill algorithm: your search would be broadcast to all connected peers, which would broadcast it to all peers that hadn't seen it yet, until somebody responded with the file and their IP and you could download directly from them. Interestingly Ethereum uses basically the same algorithm for block distribution, with some optimizations that were first published by RTM, who was one of the founders of YCombinator.

Kazaa's innovation was to split the peer space into "ordinary nodes" and "superpeers", with the observation that not all bandwidth links were equal. It would enlist hosts on high-bandwidth connections to form quasi-centralized indexing nodes to organize the network topology for all the low-bandwidth consumer nodes. It's a similar principle to how the Lightning Network works for Bitcoin, or how L2s on Ethereum operate. This also made it easier to shutdown than Gnutella though, because being a superpeer made you a legal target for the RIAA.