When a user (let's call him Joe) gets onto a Gnutella network, his client creates a list of users to whom it considers itself directly connected. That is, it considers those users to be one "hop" away.
Joe then searches the networks for a file. His client then sends a query to all those users who are one "hop" away. If none of those users have the requested file, Joe's client reissues the query. This time, it goes to all users who are one hop away, and those users then forward it to all the people they consider one hop away - all those people who are two hops away from Joe. If none of them have it, Joe reissues the query to users who are three hops away. He continues this until he reaches a limit (no more levels of recursion) or the entire networks has been searched.
The primary disadvantage of this scheme is that the traffic generated by a query increases exponentially with the rarity.