First of all, we don't know if the charge really came from the NY Department of State. This could be a company using a similar name to make it look like NY Department of State and thus get away with it, for some time, as it might be overlooked by NY residents.
Second, assuming the charge was indeed done by NY Department of State I see a few possibilities.
NY DoS might have a platform which allows paying with one credit card, then reversing it by crediting another one. It doesn't seem a good idea for the malfeasants to use a Government Agency for committing fraud, but I guess this would be an option.
A second possibility would be the following. Let's suppose John Doe owes them $200. Instead of paying, he goes to a criminal Alphonse Gabriel which agrees to pay their debt of $200 in exchange of receiving only $100. Alphonse Gabriel pays the sum with a stolen credit card, and receives 100 legit US dollars. John Doe manages to only pay half the sum.
This wouldn't be very bright for John Doe, either, as he would be located when investigating the credit card fraud, and -if found- he would have a much bigger problem that such $200 debt. But Alphonse Gabriel may not care about that.
A third option would be that a payment gateway have some unsecured system which allows a merchant to get payments stating as sender a different company (by changing some merchant id, perhaps). If then the charge-backs go to the NY Department of State, which might not scrutiny much the charge-backs it gets, that could be profitable. Or, if it was the result of a misconfiguration (e.g. a small shop which is charging everyone as the NY Department of State) this could be similar to the first case.
If there was a small company appearing as "NYS DOS CORP 518 473 8 ALBANY NY", it may not be much noticed by the people who knows what that charge is for, and only raise suspicion when they receive some fraudulent purchases which end up on completely random people statements.
A fourth possibility would be that it somehow was legitimate (maybe some proceeding that is handled out-of-state? or a contractor of several states that issued your charge with the wrong sender?)
Finally, remember that you can dispute the charge at your bank, and have it reversed. Given that someone seems to have been able to use it, I would recommend getting a new one issued.