No nation is a "kill all" answer. They all have their pros and cons. A player either decides that nation is one he can play well, or not.
Caelum does well in cold. If he pushes a strong dominion (maybe even with that extra cold-pushing theme) then his troops will often have an advantage in combat. (ok at the moment that needs fixed but it should be mentioned for later readers)
You can fly. I know that seems obvious but I cant believe how many people seem to try Caelum without considering it. Capture the area around your castle to get the admin points. But then pick and choose your provinces. You can jump over strong indeps and hit weak ones. You have flying scouts and can find the enemy quickly in early-game. You can reach them in 3-5 hops and attack them in early game. If you jump all the nasty indeps then to reach you might take a 20 province march of attack you, attack 2 indeps, attack you, attack 2 indeps, etc etc.
You have great "attack the rear" capability. Use indeps for front-line whenever possible.
You have a flying, stealthy, lvl 3 priest! Being able to get there quick, stay hidden, and preach dominion can be very useful.
And there is always the old original Caelum hints although you have to use a wayback machine to see them.
Dom1 Caelum guide