Whether or not you can use a phone on a specific carrier depends on a variety of factors, but it is generally possible to figure it out provided that you can find enough information on the device and carrier you are interested in. The main points to focus on will be the cellular standard the carrier uses, the frequency bands it uses, and the associated bands/tech that the phone is designed for. In order for your device to operate fully on another network, it will need to meet all of the following criteria.
There are two primary competing cellular standards used throughout the world, commonly referred to as GSM and CDMA.
GSM (Global System for Mobile Communications) is generally the more widely deployed of the two standards, and is estimated to serve nearly 80% of the global market. Devices that support the GSM standard will use SIM cards to keep track of the identity of the subscriber. The 3G standards used by GSM devices are typically UMTS or HSPA.
CDMA (or, more specifically, CDMA2000) is also used in a variety of countries, but generally serves fewer subscribers than GSM in most countries. CDMA uses a R-UIM/CSIM card which serves similar functionality to SIM card. On some carriers, CDMA devices do not use any physical identity cards, and instead have an ESN that is stored on the device itself. Also with some carriers, devices that normally do not require SIM card to operate on CDMA 3G may require SIM cards for 4G access, since the 4G network uses a different technology than the 3G one.
In general, a device is therefore classified by which network it uses for it's 3G or voice coverage, so a phone which supports CDMA voice/3G but a GSM 4G network (for example, the Verizon Galaxy Nexus) would still typically be considered a "CDMA phone".
These two network standards are not compatible with each other in any way. A device built for GSM networks will not work on a CDMA network (and vice versa). Therefore, the first step in determining if your device will work on your desired carrier is to determine what networks it supports and what type of network the carrier uses. GSM Arena is a good source for device specifications, and Wikipedia is a good place to find information about carrier networks (as well as devices).
In addition to the inter-network compatibility issue, CDMA devices that do not have physical a identity card can only be used with the device's original carrier or on other countries through roaming. In most cases, carriers have a large database that contains all of the valid ESNs for their network, so only models which are sold by the carrier can be activated. This can occasionally be bypassed by altering the software of the phone to broadcast a different ESN, but doing so is illegal in many countries, and thus there is often no legitimate way to use a CDMA device on a different carrier. This restriction will usually (but may not always) also apply to virtual network operators (MVNOs) and their "parent" carriers.
As an example: Sprint may not allow you to activate a Boost Mobile phone on its network, even though Boost uses Sprint's towers and spectrum. Conversely, Sprint has approved some of their phone models for activation on certain MVNOs that use Sprint's spectrum (provided the phone is not under contract). Therefore, when dealing with CDMA carriers, your best choice will generally be to simply ask them if your model will be allowed on their network before you make a decision, since they have full discretion over which devices they will allow to be activated.
Each carrier operates their network on a specific set of frequency bands, which are typically managed at some level by the government of the country the carrier is operating in. Once the government allocates frequencies, they can usually be bought or sold by companies as they see fit (with some restrictions). In order for a device to work on a given network, it must therefore support not only the network standards (as noted above) but also the frequency bands being used.
As an example, AT&T's 3G network (UMTS/HSPA) operates in the 850 and 1900 MHz frequency bands (source). The myTouch 4G, sold by T-Mobile USA is a GSM phone (T-Mobile USA is a GSM network), but it is designed for the 900, 1700, and 2100 MHz frequency bands since this is what T-Mobile uses. Therefore, a myTouch 4G would not be able to use AT&T's 3G network because it does not support the proper frequencies. Further, there is no way to alter this by using software modifications - the limitation is created by the phone's antenna, which is specifically designed to pick up certain frequencies and ignore others.
Using the same example as above, however, you can see that AT&T operates its 2G network on the 850 and 1900 MHz bands and the myTouch 4G supports 850, 900, 1800 and 1900 MHz for 2G operation. This means that a myTouch 4G would be able to use AT&T's slower 2G network (and make voice calls) even though it cannot use the 3G network.
Similarly, it may be possible for a device to operate on a carrier's 3G network but not their 4G network due to frequency differences. Check the frequency bands your device supports for each generation of network communication (2G, 3G, 4G) in order to ensure complete compatibility.
SIM Locks and SIM Cards
Another possible hurdle in running a device on a network it was not officially intended for is SIM locks and differences in SIM cards.
Firstly, many carriers will sell their devices with a SIM lock - a software restriction that prevents the device from operating with a SIM from a different carrier. In many cases this will depend on whether or not the device is purchased at a subsidized price on some kind of annual contract. Purchasing a device at full retail price will often allow it to be unlocked more easily (or it will be provided in an unlocked state). If your device has a SIM lock, it may be possible to unlock it by contacting your carrier and asking for an unlock code. There are also third-parties that offer SIM unlocking services, but they are not officially endorsed by the carrier or manufacturer of your device. Devices will only be able to operate on their originally intended network while they are SIM locked.
An additional concern is that there are several types of SIM cards, all of different shapes and sizes. Most major carriers (and, indeed, even smaller ones) will be able to provide multiple types of SIM cards, but be sure that you get one that will fit into the slot on your device. Most commonly, phones and tablets use either Mini-SIM or Micro-SIM cards.
What about rooting?
Rooting a device is not related to the act of unlocking it for a different carrier, although the phrase "unlocking" my occasionally (incorrectly) be used to refer to both processes. Obtaining root will not unlock your device, and unrooted devices are capable of being unlocked provided with the proper SIM code. Similarly, a custom ROM will not unlock your device - it has no bearing on the SIM lock.
These Wikipedia links contain lists of cellular carriers broken down by country/region. Many of the entries also provide information regarding the frequencies these networks have deployed, or act as a jumping-off point for finding this information elsewhere.