How do you clean a pizza stone?
Perfect.  Sounds like your pizza stone is nicely seasoned.  Scrub it with your stiffest brush, rinse with water, no soap, done.  If you're paranoid about germs, cook it before cooking on it.  Throw it in the oven at a few hundred degrees, for 15 minutes or so.  

Ideally, you're supposed to heat the stone (thus sterilizing it) before slapping the pizza upon it anyway (although that requires a pizza peel).