Caelium Ores are found around the Verband, Amarkand, and Tabazra Desert maps. They show on the map as green dots as NPC do, but these are attackable objects. They must be attacked to harvest the ore, but they do not attack back.
There are 10 types and the spawn rate and locations are completely random, although there are spots you are most likely to find them. Possibly because these are the least travelled routes or are close to guards and difficult to obtain.
The most frequent places for these Caelium to spawn are in Verband and Tabazra Desert, but these are also the most difficult for lower level players to get to.. Below is a slideshow of the most common spawn sites.
This ore can only be harvested in enemy Nations, therefore it can be difficult to get. If you obtain a whole Caelium Ore, it is automatically deposited in the Nation's Altar. If you obtain fragments, these can be traded to Theletar Timur for rewards.
This ore is used to upgrade relics, therefore if you happen to see some while in another Nation, take a minute to harvest it and help your Nation out. It takes 350 of each type to upgrade a relic one time.