When you first turn your phone on, and periodically thereafter, it sends out a lower power signal which says "I'm here". (If you've ever left your phone near to a radio, you'll have heard this signal). This is usually picked up by one or more local transmitters, which then send a message back saying "Understood. Thanks". If your phone doesn't get an acknowledgement, it re-sends the signal, with a slightly higher power. It keeps doing this until reaching the maximum (around 5 watts) power. If it still doesn't get a signal, it will keep periodically sending a high-power signal to try to connect.
Actually, that last paragraph doesn't tell the whole story. Each transmitter also sends out a continuous 'reference' signal. That's the one which is picked up by your phone and provides the signal strength indication on your phone's display. If the signal strength is zero, the phone won't bother to try a connection. (At least it shouldn't. If you're in a jet, 7 miles up over the Atlantic, your phone should recognise that there's no reception and not try to transmit. The risk is that, if it does, it will send out 5 watt signal which can affect the aircraft's electronics. That's why it's important to keep your phone switched off when onboard an aircraft).
Once your phone has made contact with a local transmitter, it's simply a matter of signals being passed along a chain of transmitters (sometimes linked via satellites or landlines), to connect the caller to the recipient.
Chris