I think you answered your own question. It's right there in the quote:
He didn't know, he guessed.
Maria Hill was an incredibly high-ranking SHIELD agent for most of the time Tony has known her. (In the source comics, she gets promoted to Director at one point). She is, essentially, Nick Fury's right-hand man. She only came to work for Stark because Fury was "dead" and SHIELD was disbanded.
Tony's not an idiot -- he's actually one of the smartest people on the planet. When Fury suddenly reappears in Tony's life, of course he's going to immediately assume Fury's former second in command knew he was alive and kept in contact with him.
The fact that he guessed right merely proves how smart he is.