While The Chronicles of Narnia do not describe the Calormene religion in great detail, they offer a number of clues that give insight into the belief system. For example, Tirian described his childhood visit to Tashbaan and noted that the temple of Tash contained a statue of the god. This story illustrates two key points; that the Calormene religion had established centers of worship, and that it made use of idols (at least with regards to Tash). The Tisroc, the Calormene head of state, claimed descent from Tash, and Aravis Tarkeena mentioned that her father's family was "descended in a right line from the god Tash". While these claims may have simply been metaphorical (Calormene speech/storytelling is typically highly embellished), descent from the divine - or political authority granted by the divine - are common elements in several real-world belief systems. Both have been used by rulers throughout history to boost their status and prestige.
Aravis described a ritual performed by Calormeme women in preparation of marriage: the bride-to-be would go into the wilderness and perform three days of ceremonial sacrifices to Zardeenah, as an indication that they were leaving the goddess' service when they married.
Based on this information, the Calormene religion seems to be a formalized belief system, with at least some proscribed methods of worship. It also seems to be tied into the structure of government (though it is unclear if that government could be considered a "theocracy" in the strictest sense of the word).
It has been widely speculated that C. S. Lewis was comparing the Calormene religion to Islam (though its followers, Muslims, are strict monotheists, not polytheists); Lewis, though, had also praised aspects of Islam in some of his works and the name "Aslan" means "lion" in the languages of many Muslim countries.