+1 on Four Mile Creek SP. Nice sites, right on the lake, and your sticker lets you park at the state parking lot close to the falls for free. Definitely go on both sides (US & Canada), different experience and views. If you park in the lot on the US side it's an easy (and cool) walk over the bridge to the Canadian side, just don't forget the passports. You can get the Maid of the Mist on either side (a must) but they have different packages with other stuff. We especially liked the Cave of the Winds tour on the US side - you hike out onto a deck where you are standing right under the Bridal Falls - they show it on one of the Thompson Watersealer commercials.
Cave of the WindsThe comparable tour on the Canadian side where you "go under the falls" was disappointing - you're in a concrete tunnel and look out a little opening and see the backside of the big falls, much more fun to walk out in your souvenir poncho and flip-flops and have it crashing over you. If you have time head east and check out the Finger Lakes area of New York - lots of state parks with waterfalls (smaller) and tons of wineries.