How does a GSM network route internet packets? Does GSM use NAT based PAT like a physical Router? For example, user A visits website #1 and user B visits website #2. how data of website #1 are given to user A instead of B or both of them?
IMEI is provided by equipment manufacturer for the mobile. It is stored in EIR via the network operator while registration. IMSI is a combination of MCC(Mobile country code), MNC(Mobile Network code) , MSIN(Mobile subscriber Identification number) and is stored in SIM. There are several such identifiers based on the mode of operation to uniquely identify a user.
GSM is a combination of TDMA/FDMA. Each BS is assigned one or more carrier frequencies which is then divided in time, using a TDMA scheme, into 8 time slots. The time slot usage is such that the mobile does not recieve and send it the same time. That is, the MS uses one time slot for transmission and one for reception.
The BSS acts as a radio resource manager and allocates a traffic channel (a radio channel and a time slot) for every MS once authenticated and informed by MSC. Each MS operates only over the provided radio channel in the given time slot.
In GSM, the RR protocol between the MS, BTS and BSC(BSS) does the routing of the data to the recipient and you can consider it to be similar to that of network layer(layer 3 of OSI). The routing of data is further coupled with SCCP for end to end addressing/routing in SS7.
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.