In the summer of 1945, although it wasn't part of his regular duty in the mess hall at Camp Lejeune, Tyssens helped his buddy open a crate of canned tomatoes. They spotted the label Shives had placed in the crate four years earlier, grabbed it and each got half.
"That shows you how fresh our food was," Tyssens says with a laugh.
Tyssens got the part with the address, and he could speak English, so he wrote to a then-17-year-old farm girl.
One day in September Mary Ellen Shives stopped to get the mail as she came in from working in the fields. She was surprised to find a letter addressed to her. It was written in red ink, and the enclosed photo - the only picture Tyssens had of himself - had a red mark to let Shives know that he was the guy on the left.
Shives says she always had admired Holland and wasn't "going with anyone," so she wrote back.
More letters were exchanged, and Tyssens wanted to visit but couldn't get leave before December when he shipped out to Indonesia, as part of the force engaged in guerrilla fighting to regain the former Dutch colony for the Netherlands.
The young marine and his American friend wrote to each other about once a week during the 30 months he was in the Pacific. Through their letters, they came to know each other, their hopes and dreams, and friendship turned to love. Tyssens concealed a ring in a bar of soap and sent it to Shives, asking her to marry him.
Shives said she never thought anything like this would happen to her, "a little country girl." She accepted his proposal.
Instead of returning to the Netherlands, Tyssens got special permission from an understanding commanding officer to return to America. One of 12 passengers on a Holland-America freighter, he traveled for more than 50 days, finally disembarking in New York City. He got to Baltimore, then Hancock by bus. By the time he took a taxi to Elwood Shives' farm, he had run out of money, and his future father-in-law had to pay his fare.
Tyssens had a two-month visitor's visa and had to be out of the country by Sept. 24. He worked at a nearby orchard owned by Stanley Fulton, a businessman who would help him again later on.
Mary Ellen Shives and Nicky A. Tyssens were married Sept. 22, 1948, in the parsonage of St. Paul's Methodist Church in Hagerstown. They spent their wedding night riding a bus to New York City. Mary Ellen Tyssens' suitcase, which contained all their critically important papers, was mistakenly put off the bus in Philadelphia. The luggage arrived and they just made it to the ship that would carry them to the Netherlands.
But it was not smooth sailing yet.
"She was in a cabin with two Dutch ladies," Nicky Tyssens says. His roommate was a Swiss science professor with a long beard.
Accommodations were adjusted, but the bride was seasick for the first couple of days of the nine-day voyage.
Maastricht, Nicky Tyssens' hometown, welcomed them with a banner and music.
It was not as easy to immigrate to the United States in 1948 as it is now, Nicky Tyssens says. They were in Holland for six months, waiting to return to America. Fulton, the orchard owner from Hancock, agreed to serve as Nicky Tyssens' sponsor.
The couple sailed back to America with a "stowaway." Mary Ellen Tyssens was expecting her first son, Larry Roger Tyssens. Nicky Leon Tyssens, his brother, was born in 1950.
No one in Nicky L. Tyssens' family - not Nicky, his wife or their two daughters - will eat tomatoes.
Mary Ellen Tyssens has told them they should have tomatoes on a pedestal. Tomatoes are what got everything started.
Despite incredible odds, Mary Ellen Shives and Nicky A. Tyssens found each other. She recalls that some people said it wouldn't last.
Nearly 50 years later - they will celebrate their golden anniversary on Sept. 22, 1998 - those people certainly have been proven wrong.
Happily ever after. Just like a fairy tale.