Ask around in taverns and the town about the spy. The citizens will give you specific details about the spy (e.g: beard, no markings, sword). Once you have enough details (the game will tell you this), go around the town's gang areas. Each gang area has a few eligible NPC contenders that may be the spy - look around and try to match the details to the contenders. If there are none of the contenders in a gang area that match the spy's features, move on.