An interesting mystery you have. I did a browse of the major references online and found part of the problem. "Tiene" is not a real French surname, it's either a misspellingor an "Americanization" of a French name. Most likely it's Etienne or Tinon, but I saw a few references to "Henriette King", which means it could also be LeRoy or Larue. It's almost certain that the only marriage record you'll be able to find is a church record, but then comes the next problem...where were they married.
Logic tells us that if they're French-Canadian, which is very possible for that period (I'll explain later), then they left Quebec, travelled through the Great Lakes region, across the Illinois prairie and down the Mississippi. Mobile is right on the route.
The odds are against them being directly from France (possible, but not probable). We all think of the Louisiana Purchase and assume it was all a French colony. But you're looking a good 80 years before the Louisiana Purchase. In fact, you're looking before the Acadian exile. At that time the entire area belonged to the Spanish empire. The King of Spain was related to the King of France, so French Canadians were welcomed to explore and settle, but there wasn't major immigration from France just yet.
There were a couple of different Tessier-Lavigne lines wherechildren or grandchildren were voyageurs in the Mississippi region--Jean-Baptiste and Ignace both had descendents there during that period (there may have been others, but I don't have them in my records). The problem is linking YOUR Pierre to a father. From the looks of the other research out there, it hasn't been easy.
Adding to your woes is that Lavigne is a 'dit' name, so the marriage records will have the actual family name...and you don't know Henriette's real surname, so your research is going to be a huge process of elimination. In fact, Pierre may actually be "Jean-Pierre" or any of a dozen other names...or even a nickname.
Were they married in Canada? Maybe. I checked PRDH and didn't find them, but that's just a cursory look in the database with what you have. If the info you have is inaccurate, then they may still be there. Other places to look would be the missions along the Great Lakes (St. Ignace, Fort Ste Marie,etc) and the French settlements along the Mississippi (Kaskaskia Illinois, Cape Girardeau MO, etc). It's going to be tedious, but you'll probably be able to find them. I doubt the records are online because you're in the period of exploration and most of those records are still under copyright by various authors who published them in the last 20 years. But you might get lucky. What might really help is to get a copy of the marriage records of their kids in Mobile and a copy of their death records from the archdiocese or parish that's got them and get more concrete info to work from.
Hope it helps. Drop a line anytime and we'll try to help however we can.