In Final Fantasy XII: Revenant Wings, I named the ship as the "Namine". In Kingdom Hearts, I created a badass Gummi Ship which I named the "Archades". Notice a pattern emerging here?
Yeah, I'd probably have a fleet named after different FF/KH people and places. The cruisers could be named after the characters who I deem to be most powerful or skilled in some way, the destroyers would be named after weapons (Masamune and so on), and the frigates and landers and such would be named after places. The flagship would probably be the "One Winged Angel", as this really would instill fear in all who saw it.