When agents do not know where to find a match, they search. However, agents could direct their search to agents who strategically choose a certain signal. Introducing cheap talk to a model of sequential search with bargaining, we find that signals will be truthful if there are mild complementarities in match production: supermodularity of the match production function is a necessary and sufficient condition. It simultaneously ensures perfect positive assortative matching, so that single-crossing property and sorting condition coincide. As the information from signals allows agents to avoid all unnecessary search, this search model exhibits nearly unconstrained efficiency