GSM data networks (GPRS, LTE etc) allocate IP addresses to end devices (Mobile Phones) just like any other network.
As to whether NAT/PAT is used, this is entirely carrier dependent - based on a factor of how big their subscriber base is and how many public IPv4 addresses they have available.
In Australia, the incumbent telco Telstra uses a CGN (carrier-grade NAT) to support the massive numbers of 3G/LTE subscribers currently using it's network. All devices using their default APN are allocated an address from 10.0.0.0/8, and then NATted to the Internet. Public IPs are available, but only on premium services.
In markets where IPv6 is more established (eg: much of Asia), end devices are more likely to be provided with a public v6 address, requiring CGN only where the content being viewed is v4 only.
There are two types of wireless extenders. First would be an extender that uses some sort of mesh technology. This type of extender is typically only found within an enterprise deployment and will establish a connection to the network in addition to also acting as an AP. Often a mesh device will use two radios, one providing the "back haul" and one to provide client access.
However most devices referred to as wireless extenders fall into the second group and are actually just repeaters. When a wireless repeater receives (or "hears") a frame, it will then transmit a copy of that frame into the air. Naturally it will only hear frames on the channel to which it is configured, and typically will also be configured to only re-transmit frames for a particular SSID or BSSID.
Since RF is a shared resource, this repetition of data can result in a significant loss of performance. To reduce this impact, some repeaters are smart enough to not repeat frames where it hears both the frame and the acknowledgement between the AP and client device, but others are not and will re-transmit all frames. Even if you are using a "smarter" repeater, if the client is too far from the repeater to be heard, all AP traffic will get repeated leading to the same loss of performance.
When a device connects to that SSID, what exactly happens?
When a client device connects, it goes through an association process with the access point. If the client is out of range of the AP, but within range of the repeater, the repeater will re-transmit the client frames as well as the return frames from the AP.
How does the device know that base station and range extender are part of the same network and no third party can impersonate another range extender on the same network?
The device doesn't. When function as a repeater, the repeater itself doesn't really have any "identity" on the network (any management interface on the repeater is a separate matter). It is merely repeating the frames that it hears unchanged.
Even if a third party does place a repeater on in the area, this is not really a problem as the client device is associating (and establishing encryption) with the access point itself and not the repeater.
Then, what happens if the device moves around and signal strengths change? Is there some kind of renegotiation going on?
With most repeaters, there is no roaming or renegotiation. The client device will either see the frame from the original AP, the repeated frame from the repeater, or possibly both.
What does the range extender actually do? Simply rebroadcast whatever it gets from device and base station, or is it more intelligent than that?
See above.
Best Answer
In this scenario, your phone has at least two network interfaces: WLAN and 3G. Each interface has his own IP address and mask. They usually install as two routes on the phones routing table, the locally connected network and a default gateway.
Let's see a simplified example:
Interface: Wifi IP/mask: 192.168.10.10 255.255.255.0 Default gateway: 192.168.10.1 (your home router)
Interface: 3G IP/mask: 10.10.10.10 255.255.255.0 Default gateway: 10.10.10.1 (your next hop to ISP)
Resulting routing table:
Destination Interface Metric
192.168.10.0/24 Wifi 0
0.0.0.0/0 Wifi 20
10.10.10.0 3G 0
0.0.0.0/0 3G 30
So, what happens when your phone wants to send a packet? It checks the destination IP address vs its own routing table and decides which interface to send it to.
In personal devices, this metric is automatic. Your iphone is smart enough to set a lower metric to Wifi.