I went back to the video and it said Gemini was "searching" for that music, not generating it. Google has done some stuff with generative music (https://aitestkitchen.withgoogle.com/experiments/music-lm) but we don't know if they'll bring that into Gemini.