Here is a fascinating post on how people used the margins of books for notes. The most common other note-taking implement was the wax tablet, of course.
But slips of parchment (left overs from cuting the pages for books) were also used Apparently there was a guide book called De discipline scholarum "for students and teachers at the University of Paris" that explained "how a student should bring such slips of parchment to class for taking notes." It dates from 1230.
I wish I knew more about the medieval practices.
1. See also here.