Gnutella is a true P2P network; i.e. with no central servers. Instead, the user's computer is linked with many others.
How it works [2]
Once the other computer "hears the hello", it lets other computers that it is connected to know that it has established contact with the new computer. Each of these computers in turn let several more know of the connection. And so on, and so on, and so on - just like the shampoo ad.

The user types in their query.
The user's computer sends the query to the computer it's connected with, and it in turn sends out the requests to the computers it's linked to. And so on and so on - well, you get the picture.
All the contacted computers search their hard disc(s) for the requested file. If it's located, they send back the file name and their IP address to the computer that initiated the search via the linked computers.
A request has a "time to live" (TTL) limit placed on it - basically this prevents the search from going too deep along the computer grid. Even with this, one search will typically reach around 8000 computers before it stops propagating!
The user then selects the file name they're interested in, and their computer directly links with the computer that has the file on its system (remember, it sent its IP address with it so a direct link could be made). If several computers have the same file on their hard drive, the user's computer can download from all of them simultaneously, thus decreasing the download time.
C'est tout!