Windu probably assumed Maul was a Sith because he knew he wasn't anything else. I'm sure the Jedi kept tabs on all of their members who leave the Order, and they knew none of them had on rogue (or perhaps it is as simple as none of them were Zabraks).
It was probably a combination of factors that made Windu think Maul was a Sith as opposed to a member of one of the various other Force-using organizations in the galaxy.
First of all, Maul was able to beat Qui-Gon in a lightsaber duel. Obviously, Jedi are killed from time to time, but not in a lightsaber duel like that. In addition, Qui-Gon was a very powerful Jedi, on the level of a Council member. (The only reason he wasn't on the Council was his unorthodox methods.) Besides the Jedi, the only Force-using group that trained in the use of lightsabers were Sith or Sith-affiliates.
The red lightsaber would have been a factor, too. As far as I know, there had not been any red lightsaber users who were not Sith/Dark Jedi at that time. Obviously, no Jedi would make a red lightsaber, and just as only the Sith were the only others capable of wielding a lightsaber, the Sith were also the only others capable of constructing a lightsaber.
In addition, the existence of Sith would explain the increasing darkness in the Force that the Jedi were already feeling. The Jedi could observe that none of the other Force organizations were increasing in power.
It's important to remember that there would have been very little distinction between "Sith" and "Dark-side user" in Mace Windu's mind. So far in the history of the Sith, more or less all Dark-side users were Sith. It was only after the establishment of the Rule of Two that the definition of Sith became more discriminatory.
See also: When & How did Yoda come to know about rule of two?