The hat was sorting students into houses according to - what seems to be - "what's in their head".
How is that possible? In Harry's case, he spoke to the hat, but most students just sit there silently from what I remember from the books!
I was going to guess that the Hat is able to read student's thoughts, but someone had that thought before I did:
The Sorting Hat is one of the cleverest enchanted objects most witches and wizards will ever meet. It literally contains the intelligence of the four founders, can speak (through a rip near its brim) and is skilled at Legilimency, which enables it to look into the wearer’s head and divine his or her capabilities or mood. It can even respond to the thoughts of the wearer.
Source: Pottermore (aka JKR herself)