I'm especially interested if ship naming was endemic to non-European cultures such as China, Japan, Polynesia etc.
Ooh, this is exciting, I get to cite one of my old professors!
He estimates that people - or at least Greeks - started naming their warships by 480 BCE. One of my favorites is the octoreme Leontophoros, built by Lysimachus (one of the diadochoi).