Where would be the best place to go to try and trace where the marriage took place and obtain a copy of said records?
Wlodawa town hall would be the obvious place to ask. Most gmina offices in that area seem to have fairly decent amounts of records and, from the times that I've been tracing people out there, the office staff are very willing to help (although you're unlikely to get far trying to communicate only in English). Wlodawa, by the way, is a very nice little town and the area is well worth visiting in spring and early summer (after that the mosquitoes do get a bit tiresome).