Got my PCC today in Dakar, Senegal. I am a non-resident so i had to get it in the capital's department of justice.
The name of the document is "Extrait du Casier Judiciaire". The officer took my original passport after I filled a request form with details of parent's name, locality where I stay in Senegal, occupation, mobile number, and a nominal fee of 200 CFA. It took me a day for getting this certificate.
All non-residents have to apply in the below mentioned address:
Du Tribunal Departemental de Dakar
Bloc Des Madeleine
Avenue Andre Peytavin, Dakar, Senegal.
For Senegalese citizens they can obtain the certificate from the respective department of justice in their localities.
For former residents, it is given in some websites to apply by mail to "Ministry of Justice", Dakar (But i could not get this verified today)
Though it is an old thread, i thought it would help someone in future.