Another ship naming question (REAL ships this time)

When did systematic usage of ship name prefixes, like HMS and USS, start? What navy was the first to equip every vessel with such a prefix?

For U.S.S., the practice was first made official by President Theodore Roosevelt on Jan. 8, 1907:

It was started, like nearly every other great naval tradition, by the British. It was used to differentiate private ships from those owned by the Crown. Its use predates the American Revolution, but I don’t know by how far.