Lots of great advice above that I'll try not to repeat.

Private schools vary a lot and public school gifted programs vary a lot so it is impossible to say what will be the best fit at this point. Some things (many of which have already been said...) I'd look for

1. flexibility - schools that brush your questions/concerns away with easy "we've had lots of gifted students" and think they have all of the answers... often don't. Keep asking questions, ask for examples and specifics. One of my favourite advocacy moments was in a VP's office many years ago when I was assured that differentiation would solve all of my DS's problems. I asked for a specific example in science (he was in grade 1 and would sometimes get us to read university physics books for bedtime stories....). Her example - "while the other kids are learning that plants use air, water and soil to grow, he can learn that it is called photosynthesis" She even said photosynthesis real slow to make it sound more amazing. I smiled and knew we weren't on the same page.

If the school says they can work at their own level - ask if they have any examples of kids working several grades above level? How is that handled? Is gifted enrichment viewed as an add-on or extra? - after you do all of your normal work THEN you can do an extra worksheet (oh boy!!!).

Is their way of accommodating isolating? Is the solution to have the child sit in the corner and teach themselves grade x+y math while the rest of the class does grade x.

2. peers - some gifted kids are great at blending in with others and/or have a variety of interests that aren't all "out there". Others stick out and NEED intellectual peers to discuss their odd passions with at recess. If your child is one of the later types then the potential peer group can be key.

3. what is the gifted program and who is in it. What is the criteria for entrance? Is it focused on the high achieving type of gifted kids? (that is fine if that is what your child is but throwing a 2E kid into that might not be so great).

What does the program actually do that is different than the regular program? Have the teachers taken extra courses on gifted children and their needs? Is there a high turnover or has this teacher been doing this for years?

4. teachers and their fit with your child - as many have stated they can be the difference between fantastic and disaster.