Gonzo-
Aside from Al's typically thorough suggestions, you should not be alarmed at what is expected of you for any Navy work. If you have worked with any of the ASME or AWS Codes then you will easily relate to Navy welding requirements. They have a different emphasis on essential variables, different permitted base materials, limits on welding wire & fillers, record keeping, etc., etc., but the method to qualify procedures and welders is very much the same. I suspect your company will be a shop oriented "build-to-print" operation and one happy thing to keep in mind is that every Government procurement office has an equipment specialist or equipment engineer that should provide you with any technical guidance that you may need on the equipment or components you are making. If your contract requires you to submit weld procedures for NAVSEA approval, then the contract will detail how to do this. If your contract does not specifically tell you to submit procedures for NAVSEA approval then the Level III individual that Al mentions may have procedure approval authority. You should clarify this with the contract specialists.
One spec that Al didn't mention is Mil-Std-271 which describes the methods of inspection AND also the Level III personnel which he mentioned must be certified IAW this document which further invokes another standard, American Society For Nondestructive Testing (ASNT) document SNT-TC-1A. This is a standard for certification of commercial NDT inspectors. So your welding Level III can be either certified directly by NAVSEA or (more likely) certified by an ASNT authorized school. Either certification will be valid in the eyes of the Mil-Std-278 folks.
If your company does not already have a Level III on staff, you may need to consider hiring an outside consultant for this purpose until you grow your own Level III. Just as you will likely hire an NDT company for RT examinations, you can hire an NDT company to fulfill the Level III weld related requirements.
Write back if you have any specific questions.