Welcome to the forum.
Rocketry is great hobby for you and your son to enjoy together. I am sure you will both have lots of fun and learn a lot.
I have no idea about the legalities, but I do have a few issues with the CO2 rockets in that video:
1. A lightweight paper rocket with a heavy CO2 cartridge sticking way out the rear is very unstable. As you can see in the video the rocket flies off at a horrible angle. This is unpredictable and somewhat dangerous. To learn more its worth Googling the relationship between Centre of Pressure (CP) and Centre of Gravity (CG).
2. The rocket doesn't have a parachute or any sort of recovery mechanism which means:
a. It will come down quickly which is quite dangerous. I wouldn't want your son to be hit by a falling CO2 cartridge.
b. The paper rocket probably won't survive the landing, so your hard work will be destroyed. Not a great way to keep kids interested.
c. You miss out on one of the great pleasures of rocketry, which is seeing a parachute open and watching your rocket float down in a controlled manner. Kids really get a thrill from this.
3. The rocket doesn't fly very high, so the flight is very short. Not much fun, especially for kids.
4. The launch mechanism doesn't look particularly safe, especially with kids around. It could easily be launched prematurely.
As George suggested a simple water rocket launch mechanism is not that complex to build. Probably easier to build than the medieval CO2 cartridge piercing mechanism in the video.
If you don't want to go with water rockets then consider black powder rockets. Estes make some great starter kits that include a simple to build rocket, a launch pad and a launch controller. Lots of people get nervous about black powder, but its quite safe if you follow some simple safety rules. I would argue that its much safer than CO2.
I am not sure where you live, but its worth investigating if there is a rocket club in your area. Clubs hold launch days where you can:
1. Learn lots from other members.
2. See loads of other interesting rockets fly.
3. Get your rockets checked by an experienced safety officer.
4. Use club launch systems.
5. Fly with the reassurance of the club's insurance.
Good luck on your journey and keep us updated. This a great place to ask questions.