Depends on the phone, but either way your first step is the cell (network) provider.
But it's not cheap even for the cell company to locate, so it's rarely done.
We look for corporate customers if they are large enough and freak out enough (it's the CEO's platinum phone with the only images of their child's first steps), but really it's rarely done unless the user is willing to pay a premium, and even then it has to be the right type of phone that can be tracked without software already installed on it (most newer blackberries, some smart phone).
If you had added tracking software prior to the loss that would've been best, but without it it's more complicated and involves man-hours on the network side at the engineering level. You might want to look into adding software to your next phone.
Really your best chance is that it's picked up by someone scrupulous, not the type of person who comes here asking how to unlock the phone they just found as if it were a shiny penny on the ground and not something that could very easily be tracked and returned to the owner.
Good luck, but really, you're pretty likely out of luck.
Actually, I thought you could take your IMEI to your service provider and ask them to help you with it. If they can't find it, at least they can block that IMEI from their networks, rendering the phone useless to people with limited knowledge of cellphones.