It's not that it's impossible to braille without braille paper; it's just that the resulting braille does not last very long and may be harder to read later. Also, in some cases with very thin paper, you might stab straight through it. This makes more of a tiny frayed hole than a true braille dot. I have brailed on other types of paper, especially printer type, and it works fine. In fact, in my opinion, it might even be easier to slate on printer type paper since you don't have to push down as hard. However, everyone I know has learned to slate on braille paper, so I don't know how true this is in practice.
By the way, notecards work great! If you get the little slate, a lot of them are sized to fit a standard 3\*5 card (I think that is how big they are).
If you want some weirdly detailed info on braille paper, you can read this publication by the United States Library of Congress:
$1Remember to get a good stylus (those things can suck if you hate the grip), and that Mx. Slate thinks it's always opposite day, a great time to be backwards. Have fun slating!