Chromatic Passing Tones
Using bebop scales is a great option because they contain chromatic passing notes, which is the sound you're looking for. There are many different bebop scales:

By adding a chromatic passing tone, these bebop scales gain something valuable: the downbeats emphasize chord tones. For example, looking at the C major bebop scale, the notes that occur on downbeats are C-E-G-A. These notes spell out a CM6 chord. The downbeats of the C dominant bebop scale spell out C-E-G-B♭, a C7 chord. The C melodic minor bebop scale spells out C-E♭-G-A, a Cm6 chord. And the C harmonic minor bebop scale spells out C-E♭-G-B♭, a Cm7 chord.
These scales teach us that it's important to think about where we want to introduce non-scale tones.
Another way to introduce non-scale tones is to approach notes chromatically. Chord tones, for example, can be approached from a half step below or from a half step above. Between the two, it's more common to approach a chord tone from a half step below. A common improvisational exercise is to surround chord tones. In the example below, I'm surrounding each chord tone of CM6 using a half step below and a whole step above:

Chromatic Passing Chords
The video you shared doesn't contain many chromatic scale tones (only one that I heard). What you're hearing in that video is related--chromatic passing tones. The video also contains more complex progressions that, while non-diatonic, are still very standard.
The progressions you hear in the video almost certainly aren't being improvised. But to develop an ability to improvise chord progressions, you need to learn songs and build up your vocabulary of chord progressions. Start out by transcribing the chords to the song you linked to. Find other jazz songs with similar progressions, and take note of where they differ. As you expand your vocabulary of known progressions, you'll develop a variety of choices you might decide to use on-the-spot while improvising a progression.
Some of the non-diatonic progressions you'll hear in that song alone include:
| IV Maj | ♯iv dim | I64 | V7 | I Maj |
| IV Maj | ♯iv dim | V7 |
| V7 | ♯v dim | vi min |
| II7 | V7 | I Maj |
(note the II chord is dom7 rather than min7)
| I Maj | ♭iii dim | ii min | V7 |
| ii min | iv min6 | I64 | V7 | I Maj |
The best way to practice these is in context. Transcribe interesting chord progressions that you hear, play them on your instrument, try modifying them, and try combining different progressions. Categorize their function ("this one is a nice turn-around," etc.).
| ii min | iv min6 | I64 | V7 | I Maj |
. You're latching on to those more complex progressions. The recording almost certainly isn't improvised, btw. – jdjazz Jun 20 '18 at 18:22