There are a few ways I might approach this experimentally:
(1) - Strip a pencil down to the cylindrical graphite core (or simply use a mechanical pencil), weigh this core to obtain a value for $m_{core}$, and then counting as you go, draw fixed-length lines on paper using a straight-edge. After some time, weigh the remaining section of the core to determine $m_{used}$, i.e. the mass of graphite was used to draw $N$ length $L$ lines of ~1mm width $W$ (or whatever you can sample from your lines). The mean thickness of the line, $T$, would then be:
$T$ = [(weight of used graphite) / ((estimated density of graphite) * ($L$) * ($W$))]
Unfortunately I was unable to find a more accurate density of graphite than $2.09 – 2.23 \frac{g}{cm^3}$ (on Wikipedia: http://en.wikipedia.org/wiki/Graphite), so you might want to determine that yourself beforehand by measuring the length and circumference, and thus the approximate volume, of the cylindrical graphite core for the pencil you care about. You can then trivially compute the density using, $m_{core}$, the measured value for the core's mass.
(2) - Finding $m_{core}$ and $m_{used}$ as in (1), we can perhaps improve the process of calculating the surface area of paper we've covered in graphite. Here, we take a sufficiently large piece of paper, and instead of drawing fixed-length lines, we densely cover the paper with graphite under the two constraints that no sharp angles are generated and that no two line segments ever cross. The purpose of these constraints is to insure that one isn't retracing over a previously deposited layer of graphite.
Next, either scan the piece of paper at high resolution or take an overhead shot of the piece of paper with a high revolution digital camera. Then use Mathematica/Matlab/etc. to count the number of light vs. dark pixels using a threshold function that comes as close as possible to estimating an the line's thickness at a few experimentally measured points (presumably using a ruler and a light microscope). My guess is that this will provide a better estimate of the surface area covered by graphite than spline interpolation/etc. since it should catch variance in line-width thickness, $W$, subtract 'spray' where chunks of graphite chip off and deposit away from the line (and would otherwise cause an overestimation of line thickness), and so forth.
As before, we then have:
$T$ = [(weight of used graphite) / ((estimated density of graphite) * (surface area of paper covered in graphite))]
Where "(surface area of paper covered in graphite)" = (number of 'dark' pixels) / (number of 'light pixels') * (surface area of scanned/photographed paper).
Ideally one would like to directly use visual light transmission to compute the surface area of a piece of paper covered in graphite. Here, one would compare the measured transmission value for the graphite-covered paper with a control measurement for the previously clean piece of paper, and the piece of paper with a known surface area covered in graphite. In practice though, considering the problems with detector non-linearities, the possibility of non-linear scaling of opacity with graphite thickness, etc., you'd probably be better off with the scanner or digital camera and a threshold function.
As for some experimental predictions... I think Tim did a pretty reasonable job considering the large number of possibilities for pencil lead size/darkness/hardness/blackness/etc. Referring to the "HB" scale (for hardness and blackness) I could certainly expect a difference of an order of magnitude or more in the thickness of a line generated using a 6B pencil vs. a 4H pencil (http://davesmechanicalpencils.blogspot.com/2006/04/lead-size-hardness.html).