I have not sailed from NO since Katrina, but assuming that nothing has changed here's the scoop. There is a parking lot adjacent to the terminal (on the dock). I've parked there several times and never had a problem. It is fenced and supposedly guarded 24 hours a day. There is an overflow lot also at a nearby hotel. It is covered parking and a shuttle bus runs between it and the pier every fifteen minutes or so. I've parked there also and had no problems.
As I recall, rates were about $7/day, but that could have changed. At one time you could pre-pay your parking through the cruise line but I do not know if that is still an option.
We sailed the Sun in November and had a wonderful time (even though it was from Galveston) and are scheduled to sail her again this coming November. It's good to have her back in Louisiana.