In many P2P applications, nodes can be classified into different types according to their interests or resources, and the routing for the nodes with a specified type over overlay networks is the key for data distribution and query in these applications. Unstructured overlays have a low maintenance cost and high robustness, but fail to ensure the routing efficiency. This paper proposes a gossip-based type sampling approach—TypeSampler, which samples the nodes of different types with the same probability (called type sampling). The type sampling ensures the lower bound probability of finding a neighbor node with a specified type at any node, and thus ensures the routing efficiency over the unstructured overlay. For type sampling, TypeSampler first implements the proportion estimation of types through peer sampling and anti-entropy aggregation based on gossip. Next, TypeSampler maintains a type sampling table at each node, periodically, based on the estimated proportion values. Theoretical analysis and experimental results reveal that TypeSampler can not only achieve precise proportion estimation and approximately uniform random type sampling, but can also work well even in the dynamic network environment. Moreover, TypeSampler can support more efficient routing and has better scalability compared to the existing approaches.