Cultural themes - Anglea, Baronies, Yesha (Well, most of the ships are Yesha to start), Guild, Arashi, Chaladon
Automoton Theme - This could serve as an Anglean theme also but just have the theme being with some automotons on board the ship. Think Bioshock vending machine style.
Pirate hunter - Bullet holes and makeshift armor patch jobs. Hash marks signifying kills. Wanted signs posted in parts of the ship.
Ghost ship - As it states, looks like an undead airship. Maybe add some eerie glow effects to it. This could be a special seasonal theme.
Christmas ship - Again another special holiday ship but with snowmen and such on board.
Air Pirate - No brainer. Stolen cargo, booze bottles, and piles of treasure.
Also, themes that change more of the stock appearance. Not just around the basic frame. So say a theme which adds more of an armored shroud to some of the balloons. Just for looks of course but it would be a good prep for Adventure mode where people would likely want customization like that.