Since his parents were of Shrewsbury Meeting, you would expect there to be some record there, but I've struggled with finding records from this Meeting for people I know were members. Donna Hay's Quaker New Jersey Meetings website notes that Shrewsbury records are apparently missing/incomplete/unavailable online or in abstract. I haven't paged through all the minutes on Ancestry (yet, this is probably in my future), but I wouldn't rely on the Ancestry index--a ton of New Jersey meetings are incorrectly named and you can't trust the indexing to include every person in the minutes. Maybe the microfilm itself needs to be looked at.
Ancestry does have a handwritten copy of an 1878 abstract of "Records of Marriages, 1674-1853, Births 1641-1869, Deaths, 1666-1876". Hugh Vail, the transcriber, explained what he was working from -- about 50 pages of marriage records kept by Remembrance Lippincott in an unbound (!) volume. I see some Bills in the index, but not Stephen and no one named Gardiner.
Land records show there was a Richard Gardiner in Middletown, Monmouth County the right generation to be her father (but I see you disconnected his daughter from Nathaniel).
They weren't married by bond (nor would we expect there would be; as Quakers they'd be married in the Meeting).
I don't think the absence of a record online necessarily disproves the marriage in this case. I'm also wondering about her specific date of birth supposedly in Eastham; was that made up? Conflated with someone who didn't leave Mass? Could they have married there?