Of course it can be done, but there are obstacles. Maine to Nova Scotia is not a short or easy ride. If they don't know boats, there's virtually no chance they'll make it. It's 50 to 60 miles, the currents out there are trecherous, like a strong, deep river, the fog is usually quite thick, it's dang cold, and they'll likely beach on the French shore, a wide open strip where they'll be spotted easily and will stand out due to language issues, if they can even find a beach. Steal a lobster boat? It will be heard, if they can even pull it off.
Some yachters make the trip. They could hook up with some crusty old bugger sailing his big old boat back to Chester. He'll fly his Canadian flag, they can overhear him planning the trip and know he's alone. They could stow away. He could be sympathetic.
The New Brunswick border at St. Stephen is not hard to get across. They could steal a row boat across from St. Andrews. They could almost walk it at low tide. St. Andrews is a tourist town, and they could easily steal an American car at one of the hotels or B&B's. I'd guess many of the locals don't even lock their cars. It's then a five hour drive to Halifax. They'll arrive before enyone knows the car is stolen. A heck of a lot easier than sailing Fundy.
Do you have a particular destination in Nova Scotia?