In one of her missions, she claimed that a blonde guy (from Shrina) who ran to Wutai and handed Yuffie's father all the important details about Shrina, including the mail addresses of SOLIDER. While her father is not interested in the finding, Yuffie ... just happened ... to get hold of it, which is how she contacted Zack via mail.
So, I think that blonde guy she refered to was that of Cloud. Cloud. Cloud. Cloud.