I'll often choose names based on a "theme" I'm trying to follow. Not always with success, but I try.
For example, I thought it would be nice to be the Klingons, so I had Bird of Prey, Vor'cha, and Negh'Var as names.
Recently, though, I've found that a military-style naming system works best.
I give them 1-2 letter abbreviations based off hull size and/or purpose. After that I give a number for each design. Minor variants of the same design may have a small lowercase letter suffixed instead of a new number.
For example:
An F1b would be the second minor variant of the first design created for the small (I call it "fighter") hull.
I never followed the game's names that much, "Fighter" and "Frigate" both start with F, so I use my own system.
After the military-style prefix, I usually follow it by a name. I don't have a good system for the names yet, but I'll try to find something.
I have recently stumbled across a page which includes the official naming guidelines for military aircraft, which I plan on modifying for use in the game.
OH, time I said hi! I actually got this game quite recently (yesterday), and I like it a lot! After trying it out on somebody else's computer, I went ahead and bought it for myself.
Now I'm spending more time designing ships and naming them than I am taking turns

. The flexibility is great!
I have one problem, though: Sometimes I want to go back and change the name or description of my ships. Is there any easy way to do it?