Yes, I have cruised from Norfolk. It wasn't a mega ship so there were no long lines.
The terminal, such as it is , is called Nauticus. Although small they seem to have everything together and are working through trial and error on the small glitches. If you are driving from a distance you may want to come a day early and stay at the Sheraton on the harbor.
Any other questions, please feel free to e-mail me.