The submarine sandwich is one of those interesting types of food which every city claims as its own unique creation.
When I was in Brunswick, Georgia, I was told that the submarine sandwich was invented in Brunswick during the Second World War. Apparently, the town was producing about 4 Liberty ships each month. The construction workers were too busy to stop for lunch, so a few different local shops invented and began delivering "submarine sandwiches" to them. After the war ended, about 16,000 contract workers left Brunswick, spreading the new sandwich throughout America.
A few years later, I heard the same story in Portland, Maine.
There's even more explanations for the invention of sandwiches similar in design to the modern submarine sandwich, like the hoagie:
The most widely accepted story centers on an area of Philadelphia known as Hog Island, which was home to a shipyard during World War I (1914-1918). The Italian immigrants working there would bring giant sandwiches made with cold cuts, spices, oil, lettuce, tomatoes, onions, and peppers for their lunches. These workers were nicknamed “hoggies.” Over the years, the name was attached to the sandwiches, but under a different spelling.
whatscookingamerica.net, "History of Hoagies, Submarine Sandwiches, Po' Boys Sandwiches, Dagwood Sandwiches, & Italian Sandwiches"
I imagine that a similarly colorful story could be told for each of the different regional versions of the submarine sandwich. Instead of having one origin, the submarine sandwich appears to be one of those original memes, the sort we are born with. In The Hitchhiker's Guide to the Galaxy trilogy, Douglas Adams discusses Gin and Tonic as another food based meme.