You into your ship when you are in a starbase and select the ship statue. You will see a drop down NCC and NX are both listed.
Actually you can do it anywhere...space or star dock. Here's how:
(1) Go to the C-Store and claim the item
(2) Press "K"
(3) Status (tab), iirc (it is one of the tabs...)
(4) Choose your ship name on the left
(5) Choose the rename button at the bottom of the window
(6) When the pop up comes up with your ship name, just change the prefix