Why modern cellphones do not have an externally visible antenna?
Short answer: external antennas are unattractive to the user. The consumer drives the market, and these days, consumers want thinner, lighter, faster, etc. This is actually a huge problem for antennas because the physics are fundamentally limiting.

Most antennas in cell phones are some sort of variant of a PIFA (planar inverted-F antenna). Antenna-Theory has some cool articles on PIFAs and the now-famous iPhone 4 antenna. PIFAs are fairly pattern invariant, and provide a decent impedance match. They have low gain but if you do a link budget calculation, you'll see that your noise floor is like -110 dBm (I think... I forget but somewhere in that range).

The miracle that makes phones work is digital communications. Advanced modulation, extremely robust protocols, MIMO, etc have all contributed to ensuring communication even when the antenna on the phone itself is a terrible radiator (-5 dBi gain). If you do the link budget calculation to reach the nearest tower, you'd see that it works, so long as your link budget factors in all of the communication properties. That is, you have to consider what signal level the radio (cell phone) needs to demodulate the digital data and get information. Beyond analog gain (antenna, amplifiers, etc), you have digital gain through things like error-control coding (i.e. coding gain) and robust modulation techniques like OFDM (the standard for LTE and the future). Multiple access techniques (CDMA, TDMA), and MIMO also contribute to this. If you look at the "generation standards" like 3G and 4G, you'll see where on the protocol level things get super complicated. All of this goes into making cell networks work.

There's been a huge hiring thrust in the mobile industries to hire antenna engineers to design functioning antennas for thin phones. One of the toughest challenges facing folks now is that cell phones need many antennas that all couple and communicate on the same bands. So you have to be able to integrate multiple radios and antennas on a small platform and make sure everything works. When you don't do it right, you get the iPhone 4/4S... :-)