Just from what I'm looking at in this video, though I'm not 100% sure, this looks like it can be done in: Corel Painter Black Ink (you can buy/download this on Steam) Krita Or it might be some ridiculously customized brushes in Photoshop or any other image-editing software. Hope this helps.
I've only ever really *tried* Corel Painter. In my experience, it freezes my computer for at least a second every time I do a brush stroke. There's probably way more algorithms involved to generate the effects. But Corel Painter features making brush strokes that imitate the behavior of traditional media, like paint brushes, watercolor, charcoal or pencil. Instead of the colors going on top of each other in regular raster painting in like Photoshop, the colors may actually *mix* like in real life -- yellow on blue would turn green instead of making it just a yellow stroke on top of a blue. I guess a key thing is *texture* with Corel Painter. The program comes with all kinds of brushes and easily helps you render a certain classic feel of traditional media. Though I'm sure people can do this with custom brushes in Photoshop or GIMP.