The graphite itself can adhere to paper fibers with London forces; it's not a strong adhesion because the marks can be erased easily. Some of the graphite is just mechanically stuck between the paper fibers; rubbing a mark from a soft pencil can easily blur it. Enough graphite is deposited that a line drawn by a pencil can conduct electricity.
The clay gives the lead structural integrity; an "H" pencil has a harder lead, and deposits less graphite; a "B" pencil is softer, and an "F" pencil can be sharpened to a finer point.
In my time as an art major, I made a lot of sketches using vine charcoal on newsprint. Vine charcoal has no binding clay, and the marks were easily smeared. On paper without much "bite", it was easy to lift the marks off completely with a piece of kneaded rubber, and if you wanted to keep a charcoal drawing (or a soft pencil drawing) you really had to spray it with a fixative.
So I'd say that it's possible that the binding clay also plays some role in binding the graphite or charcoal to the paper.
In the manufacture of graphite pencils, air-classified grades of Volclay sodium
bentonite and micronized hectorite are regularly used to bind the graphite
compound in pencil lead. --- American Colloid Company, Industrial and Household Applications
Bentonite and hectorite both have ionic surfaces that probably help bind it to OH groups on the surface of cellulose fibers.