After the introduction of the "simplified application process" you don't need the UK police certificate any more at the time you apply.
Once CIC has asked you to send in you documents, you go to a police station somewhere near to where you live. Depending on which nationality you are you show them your id card or your passport (or utility bill together with driver license...). You pay 10pounds and give them your address. It then takes a couple of week and they send you the police certificate directly to the address you gave them.
Please remember that you will need to provide Police Certificates from the authorities from all where you lived in the last 5 (I think) years.