I'm flying to London and would like to get a UK SIM card as soon as I can. Is it possible to buy those at Heathrow airport? Should I buy one from there, or should I order it in advance instead and try to get it delivered to my hotel? Or should I just walk out to the nearest cellular store when I get to the hotel and buy one there?
There are two types of mobile operators in the UK, network operators and virtual operators. Last time I landed at Heathrow terminal 1 there was a stand selling sim cards from one of the virtual operators between passport control and baggage claim though in central London you shouldn't have a problem finding a store of one of the network operators or the likes of phones4u or the carphone warehouse. There is normally at least one network operator store and one general mobile store per high street. If you know what you want and it's only a pay as you go sim you can normally be sorted in 10min.
If you're going to be in a city for a while its important to think about what you need your cellphone for, local/international calls, text and data and choose an operator accordingly. Other things to consider, ease of top up for pay as you go, rolling monthly contracts(depending on the length of your stay) and Coverage.
Central London has good coverage from all providers the rest of London is adequately covered again if your staying long term make sure you accommodation isn't in a blind spot on the providers coverage map. Outside of London and the main centers coverage varies form network to network so choose accordingly.
The network providers are O2, Vodafone, Orange(t-mobile) and Three and. Each of these four own their own networks, there are also countless virtual operators who use part of, one, or more than one of the four networks.
O2 and Vodafone have the low frequency ranges, However Vodafone does not offer 3G(Data) on their 900mhz network. The low frequency means you're more likely to get a signal in a confined space. However you typically pay a little more with these two providers.
Three won't let a non 3G capable phone connect to its network so if you have an older phone it might not connect. Because 3G is designed for data and not voice the call quality on Three isn't the best.
O2 have vending machines in the airport (well, they did in Manchester last year and I doubt that was a one off). 10 pounds for a sim with 10 pounds credit and you can phone for more credit/data/SMS/whatever.
The last option is the best in my opinion. I did exactly that in 2007. The nice thing is that you might compare different operators. Some of the operators even offer very interesting sim cards to call abroad. Finally I ended up using a sim card where calling home was cheaper then calling within the UK. Unfortunately for you I forgot the name of the operator :( But really there is so much choice, and most of the sim cards are immediately available. You might be able to buy one at heathrow, but I am not sure you have the same choice as on the street. Your best bet is to go to a shopping center with multiple phone stores to compare.
I have heard that some of the £10 SIMs from vending machines at Heathrow do not contain any call credit. Carphone Warehouse, and Phones4U are big multiple phone retailers that offer all the major networks; there are also lots of independent phone shops that offer SIMs from networks like Lebara which specialise in cheap overseas calls.
From your use of the word "cellular", I presume you're from the USA. Make sure your phone is a GSM phone. CDMA phones are mostly found in the USA and won't work in EU.
If not, you can probably buy a really cheap phone, along with the SIM card, in a phone shop in the UK.
A friend suggested 3 as useful if you are travelling in some EU countries eg Italy France Switzerland Scandanavia, Ireland... due to them not having any roamihg charges with the Feel at Home http://www.three.co.uk/Discover/Phones/Feel_At_Home