All my stuff is from Norse mythology.  I tried to pick them based on their descriptions.

Terran: Yggdrasill, Asgard, Valhalla, Vigridr
Desert: Midgard, Jotunheim, Folkvangr
Ice: Niflheim, Hvergelmir, Elivagar, Alfheim
Volcanic: Muspell, Helheim, Nidavellir, Svartalfaheimr
Asteroids: Ginnungagap, Mimisbrunnr, Vanaheimr, Bifrost, Utgardar, Gnipahellir
Extra Names: Urdarbrunnr, Andlag, Sokkvabekkr, Thrudheim, Okolnir, Ydalir, Fensalir, Idavollr

It works particularly well for capital ships, I've found.

Battleships: Odin, Tyr, Hermodr
Carriers: Baldr, Forseti, Njord
Colonizers: Frigg, Freyja, Yngvi-Freyr
Support: Loki, Heimdall, Bragi
Siege: Thor, Vidarr, Vali

And for Starbases, I associated a lot of them with planet names.

Nidhogg (Yggdrasill), Ragnarok (Vigridr), Jormungandr (Midgard), Jotunn (Jotunheim), Surtr (Muspell), Mimir (Mimisbrunnr), Vanir (Vanaheimr), Garm (Gnipahellir), Verdandi (Urdarbrunnr), Fenrir, Ymir, Modi, Magni, Gram, Sleipnir

Yeah, I was bored one day.  I really like the name setup now, though.  It actually helps me keep track of things much better.