Castles were originally built of dirt and timber which did not withstand heavy-duty fighting or fire. There are several resources that point to early stone castles, especially in the Arab world. Stone was costly because it took a long time to quarry and it had to be hauled/lifted into place at the site. Skilled stone masons were highly paid and often travelled whereever their skill was required. Cutting stone was very laborous work - they used chisels, hand-picks, stone axes. A few castles had facades of bricks.
This is a nice site that lists some of the different stones that were used:http://www.castles-of-britain.com/castlesq.htm
Wonderful site showing the different materials:http://www.timetravel-britain.com/articles/castles/kenilworth.shtml