First, a solid terrestrial archaeology background is invaluable to a maritime archaeologist. This will also help in the job department down the line if you want to work in the cultural resource management field. You learn a lot of neat things with a BS in anthropology but the majority of maritime work actually falls under the history departments of the following universities. I hope you are accustomed to research and writing.
Are you pursing a career on the academic side or the CRM side? What's your goal for ten years out?
Second, graduate school is vital to becoming a maritime archaeologist. Look at the big three, Texas A and M, Eastern Carolina and University of West Florida. Very competitive top notch programs with wonderful professors, great facilities and excellent programs.
I caution you to be aware that a. Jobs in Europe with the pretty clear water and awesome Roman wrecks RARELY exist for people nonnative to the country. B. You better be comfortable diving in cold dark water with 0 visibility. The wrecks you will be working/learning on you will honestly probably just be feeling. It is extremely rare to work a wreck with reasonable visibility. Disclaimer: I am from the Southeast and am speaking about the southeast. If there are practicing archaeologists who can chime in about other parts of the country please do. I am just speaking from my experience.
I also warn that it is difficult to be a diver and move into the field of archaeology. Most people follow their passion for maritime history into the field of UW arch. Diving is just a medium of transportation to get you to a work site. It is no different than driving a truck to get to a site. Shipwrecks provide a unique opportunity to view a snapshot of a piece of history at any given time. The things water preserves are incredible. The importance of these wrecks, archaeologically, contributes to the broader context of human history. You must be aware that as an archaeologist you are adding to this data set that can help to better explain the societal context of that shipwreck at the time.
Understand that diving is going to be part of your job, and sometimes that ruins the fun of diving for people. Also, a LOT of UW arch is remote sensing. Sidescan sonar, sub bottom etc. You would be really wise to find somewhere to learn these skills. Finally, diving is very costly, time consuming and inefficient. That means that unless it is absolutely necessary to dive, you probably won't. A lot of wrecks and work occur in lakes, rivers, streams, swamps and even on land. You need to be prepared to encounter a variety of different diving/work situations.
So warnings aside, find an internship or some opportunity to get your foot in the door. I would recommend a field school here in the United States with one of the schools I mentioned or an affiliated program. Having worked with people who have done over seas field schools, it has been my experience that they are not as well prepared as those who attended programs here (Unless the program is throughEdinbourough Oxford or the like). Second, more diving experience doesn't hurt but isnt vital. I think becoming a dive master will be of benefit later down the road, but at this juncture may not be that important. You are competing for spots against undergrads that have wanted to do this for years and have placed themselves in positions to get these opportunities. Some of the field schools take divers that graduated OW on Friday and have them Working on Monday. You will get the diving experience you need once in a program.
My biggest piece of advice is that you need to be sure that you absolutely love archaeology and are ready to commit to major thesis level work in a program. It is not easy at all, but learning maritime archaeology allows you to be an effective archeologist all over the world. A Spanish wreck is a Spanish wreck whether its off the coast of Florida or run aground in Africa.
I am a prehistoric underwater archaeologist and I love what I do. It is not for everyone but I have had the opportunity to dive in neat places in Europe. I have also dove awful places. You want to be proficient in the most skills that you can be in order to make yourself the most valuable person to some company or school.
Sorry to overwhelm,
best of luck.