The N'EX actually have a few trains that go all the way to Ofuna Stn. Then you can change over to the Yokotsuka line at Ofuna. If the time is not convenient, then connect to Yokotsuka Line at Yokohama Stn.
Some people had said that the Keikyu Line (private) actually runs closer to the Naval base front gate. You can also connect to the Keikyu Line at the Yokohama Stn.