My dictionary says:
navy blue
from the color of the Brit. naval uniform very dark, purplish blue
But I have no idea when it was first used in US Navy.