That depends on how much work you want to put into setup. If you just want to grab a sheet and paint, I agree with John Cavan's answer absolutely.
However, if you just want something cheap in bulk, the works aren't going to be kept, you don't care about them lasting, and you don't mind a little prep, you can use pretty much any paper you want if you stretch it first. (The video calls it "gummed craft tape", but it's really just butcher's tape)
I still use printer paper for most of my watercolor applications, because I usually scan my works into digital form and dispose of the originals, so paper weight and tooth have little importance to my finished works.
As far as a paper which will not interfere with the learning process? I think you may be looking at this from a slightly skewed perspective. Every paper is its own learning process. They all have their own unique qualities which alter the work, and none of them are especially easier or harder than any others. If you want to focus on learning technique only, I'd aim for something with a smooth finish, not glossy mind you, just with a very fine tooth. Seeing how your paints interact on a plain surface is useful when you start learning how it behaves on toothier papers. The tooth of the paper will concentrate the surface liquid and alter how much absorption happens around it, affecting bleed and all sorts of other things. Beyond that, I'd recommend getting as many different papers as you can and practicing the same techniques with all of them to learn how the nature of the paper changes the results.