I am traveling to NYC by bus next week and arrive several hours before I can check into my accommodations. I have been told there is luggage storage at the Greyhound desk in the Port Authority terminal, but have not been able to find out what that looks like (lockers? or is baggage just held behind the ticket counter?) and what the cost would be.
When I have a confirmed reservation, I have always been able to drop off my bags at the hotel, hostel, or B&B where I will be staying early, before officially checking in. This may not be an option, for example, in an AirBnB situation, but I would certainly check first with your planned accommodations. It is not as if the situation you are in is uncommon.
If you do need a left luggage facility, do note that public lockers are difficult to find anywhere in the U.S., certainly any large enough to store luggage. At this point, 16 years since 9/11, I do not imagine there are any at all remaining at any airports or rail or bus terminals.
There do not appear to be any authoritative resources on Greyhound's luggage storage offerings at the Port Authority Bus Terminal. The nearest I can find is an old Cruise Critic thread which offers
Subway Concourse Level, New Building, Baggage/Package Express counter
Luggage storage operated by Greyhound Lines
7:00 a.m. to 12:01 midnight
+1 (212) 971-6331
$8.00 per piece per day
Must have ticket on any bus line serving Port Authority Bus Terminal
Tourist-oriented ticket site NYC.com does offer a Luggage storage in New York City page listing out additional options. Several are located near Penn Station, a few blocks south of Port Authority.