I want to make flake graphite into a brick but I don't know what material will work best. Would mixing it with clay work?
Clay would work, yes. It is, after all, dirt. Adding graphite to it would only be changing the composition of that dirt.
Typically, you'd only need any sort of binding agent: If you're willing to make a weak brick, you can add some cornstarch and literally press it into a brick. You could also try things like epoxy and acrylic compounds, or things like plaster.
If you wanted to keep the composition of the brick to be mostly carbon, you could consider using chemicals like bitumen and tar, although these bricks would be more flexible (depending on the graphite to whatever ratio).