Hi,
I'm a bit passionate about New Netherland :-)

I've written some books and had some articles published on some of the early settlers, if you're curious at all, see

http://olivetreegenealogy.com/published.shtml

The online New Amsterdam RDC records show the marriage as

New Amsterdam (New York City) Reformed Dutch Church
Marriages 1645

15 Aug. Thomas Stephenszen, j.m. Van London, en Maria Bernards,wed. Van Willem Bernards

That's actually the date of the betrothal, not the marriage.

http://olivetreegenealogy.com/nn/church/rdcmarr1645.shtml

Since this tells us Thomas was from London, have you checked London Eng. records? You might find something there.

I couldn't spot Willem the first hubby of your Maria in those online church records (bpt, marriages and membership lists), but it was only a quick look.

I had a look in some sources I have and see that your Thomas was quite active in various court records. He's in Records of New Amsterdam by Berthold Fernow, many times starting in 1653 and continuing to 1655. That might be something you have, and i realize it doesn't seem like you are tracing backwards, but you never know what gem you will find in those records. Even if you find nothing on his origins, it's exciting to put flesh to the bones as it were.

For eg one record in 1655 says Thomas demands payment of 78 floriins from Thomas Reedt. Thomas R says that he and Thomas S live in Middleborgh (Newton Long Island) and so the New Amsterdam court has no jurisdiction. He then goes on to say that Thomas S with 4 others was to pay for a church which he built, but to day hasn't got his money. The N.A. court refers them to the court of Middleborgh to settle the matter.

I also checked Calendar of Historical Manuscripts for State of NY for your Thomas. Again he is active, starting in 1646 and ending in 1658 with a complaint he (Thomas) made against the magistrates at Middleborugh LI for opening a road thro his land.

One of the court records mentions a man in Connecticut that Thomas claims owes him money, perhaps there is a CT connection?

I'd get those sources if you haven't seen them already and add to your knowledge of Thomas

Also, it might be interesting to see if you can find Thomas or his wife on any of the ships passenger lists I've reconstructed for 1645 and earlier.

http://olivetreegenealogy.com/nn/ships/

There are many other sources you could check -- if you think he came to NN via Netherlands (with the 's') then he might be in the Amsterdam Archives Notarial Records. Sadly they aren't indexed except by keyword and are in Dutch....

Just some thoughts for you. Good luck