In the novel its explained in more detail. I haven't read it for a while so im aa bit dusty on this one, but... They looked at the days Paulie had been off and they showed a pattern. So Sollozo must have paid him to be off sick because he knew fredo was the weaker more clumsy charecter and that he would be the driver. Also they feed the matress rubbish to him to see how enfusiastic he was. ie. in the book it says how interested he was in where the matresses would be; he could give the other familys the info for money. In my opinion they made up the matress stuff to see if he was intersed. Giving away he was the traitor. I think.

While im here... Why did they ever suspect clemenza of seeling Vito out? Isnt he the last person to?