We will be leaving from the Brooklyn Cruise Terminal in February. We didn't want to park our new car by the water at the Terminal for two weeks, so I have looked into parking in a garage. I was not able to find anything on-line for Brooklyn (I live in Maryland), but there is a lot of parking in Manhatten. This website gives a very good listing of parking lots and appears reputable.
The most reasonable parking lots seem to be in the Gramercy Park area.
Hope this helps.