There are a load of apps that can track your phone if it's lost or stolen. The new Samsung Galaxy S range of phones has this built in (little known fact). They call the service Samsung Dive: http://www.samsungdive.com/index.do
Anyway, on my G1 I use the following:
LocService: Allows me to see on Google maps where my phone is every X minutes. You can set X on the website in real time.
Phone Finder: You send a text with a password anywhere in it (like "Heydude!") and it'll text/email back the phones current location.
SIM Checker Lite: If a new Sim card is inserted into the phone, it will email/text you all the details of the new Sim, including the network, the new phone number, and Sim ID numbers. This information would be very useful to the police.
Owner: Changes the text displayed on the standby/lock screen of the phone so it displays my contact details. Useful if the phone is lost/found.
Of course, with the exception of the app I mentioned on Samsung phones, you must have installed and set up all of these apps in advance.
So my advice would be to call your network, give them your phone's IMEI number (assuming you took a note of it before it was stolen? It may be on any contracts you made, or on the box of the phone on the barcode if you still have it), and they can blacklist it.