Microsoft Exchange ActiveSync - Contacts Storage
The contacts themselves are synced to your phone's internal memory, so they do take up space. The contacts are then updated every time the phone syncs with the server.

If they were only in the cloud you wouldn't be able to access them if you happen to lose the network connection, and contact lookup would be noticeably slower. Also, some mobile network technologies can't maintain a voice call and data connection simultaneously, so you wouldn't be able to match incoming calls to contacts, because the data connection would temporarily be disconnected.