Tony has suspected Pussy was an informant for a long time in The Sopranos, but how did he know before finding the wire at his place?
He was already looking at him weirdly in that episode, thinking he was a rat. And previously, there's a bunch of stuff. But there are never "facts" that hint at Pussy being an informant, so how does he know?
Tony had several hints of Pussy's suspicious behaviours:
In the episode Nobody Knows Anything (S01E11), Pussy and Jimmy Altieri are arrested in a card game. While Jimmy stands and lets himself be arrested, Pussy runs away from the police. Later, in front of other capos, Junior remind him that people like them don't run away like that, they face the authorities.
In the same episode, his police detective "friend", Vin Makazian, informs him that there is an informant in his crew: Big Pussy. At this time Tony thinks that, considering Vin has gambling debts to Pussy, this information may not be reliable.
This dialogue between Tony and Dr. Melfi reinforces Tony's doubts about Pussy.
TONY: What kind of mental stuff would cause a backache?
DR MELFI: For conversation's sake?
TONY: Absolutely.
DR MEFLI: With some people, the pain is caused by more responsibility than they can handle.
TONY: Well, that makes sense. I mean, he's got a lot of bills, a lot of problems with his kid's school fund.
DR MELFI: Secrets.
TONY: What do you mean?
DR MELFI: Psychologically, a secret is a heavy load. It leads to feelings of guilt which further burden the mind.
Tony tries to explain Pussy's backache with family pressure, but Dr. Melfi, by suggesting secrets, without knowing it, accuses Pussy of hiding a big secret, i.e. possibly being a FBI informant.
Later, Pussy refuses to undress in front of Paulie when they were at the bath house, which reinforces the suspicion.
Pussy disappears for a while.
In the episode Guy Walks into a Psychiatrist's Office... (S02E01), Pussy comes back with a strange excuse for his long time missing: he was at the hospital receiving a cure for his back.
In the episode Funhouse (S02E13), Tony has this dream where Pussy is a talking fish, admitting "You know I'm working with the government, right Ton?".
In the same episode, Tony finally finds the wire equipment in Pussy's bathroom.
Only we know that Big Pussy is a rat for a fact. Tony doesn't (or won't) and can only detect the clues. So in the end, it's his subconscious that tells him that.
Through his work with Dr. Melfi, Tony has been able to dig deeper into his psyche, to understand who he is and get in touch with his emotions; but at the same time, he uses her advice and analytical tools to get by in the mob, as she inadvertently helps him further his position (or often, simply survive) in it.
So after 2 seasons with her, Tony pays more attention to his subconscious, and in his weakened, sick and vulnerable state, his defences are down and can no longer deny the suspicions that have festered in him for the entirety of season 2, ever since the detective told him that Big Pussy is wearing a wire near the end of season 1, and they finally spill out in the boardwalk dream through the talking fish.
EDIT: Corroborated by Sopranos creator David Chase in an interview from the book Dying to Belong:
CHASE: Well, from the get-go this is a story about psychology. A man goes to a therapist. So those dreams are earned, because so much of psychotherapy has to do with dreams. But because its a psychological show, the dreams often have to be interpreted. Because they have to carry a point. And so – “Funhouse.” That came about because I couldn’t bear the fact that we were going to have to do some kind of procedural in which Tony found out Pussy was a rat. Like he was going to have to call up some cop, or some guy would come to him and then he’d follow up on the lead. And they’d stake out Pussy’s house. And they’d follow him to the FBI. Blah, blah. [...] So I thought, “How can he just know it?” Can’t we skip all that crap? And then I thought, well, on some level, he's known it all along. And so he could just have this terrible dream. Every time I have food poisoning, and I've had it too often, it starts off with very dark thoughts. I feel suicidal, very depressed. I'm half asleep. It's in the middle of the night. And I think, "What's wrong with me? What's wrong with the world?" It takes a while before I identify it as a feeling in my stomach. So I tried to do that. So that this knowledge about Pussy was what was poisoning Tony. And it had to be vomited out.
