Start with the light house near Constitution Bridge. There are gazillions of lighthouses.
Its very tidal.. If you want to paddle Northumberland Strait bring boots for red mud.
http://www.paddling.net/places/PE/Sea kayaking rules. Tides are about 10 feet. Several outfitters. Outside Expedions
No real rivers. Just estuaries which at low tide can be empty of water.
We had boats last year and just did a car day trip not seeing anything very interesting that we couldn't see on land. The boats we used a lot in Newfoundland
Don't bring potatoes. God knows they have enough of them there.