This term refers to a method of fitting an image onto a screen that is less wide than the image (or more square, if you prefer) in order to preserve its original Aspect Ratio. This is done by shrinking the original image until its width matches that of the screen; the side effect is that the movie's height is now considerably less than that of the TV screen, resulting in black bars at the top and bottom, forming a "box" around the film (it's rather like watching the film through a mail slot or "letter box", hence the term).
The two most common letterboxes involve trying to fit a 16:9 image onto a 4:3 screen or a 21:9 image onto a 16:9 screen, although now that 4:3 is essentially replaced by 16:9 the former has become less common.
Bear in mind that the bars that letterboxing generates are usually black, but not always. The original widescreen home video release of Woody Allen's Manhattan used grey bars. TV channels or some YouTube videos showing content recorded in 4:3 or vertical smartphone video would fill the letterbox with a zoomed, cropped and blurred version of the same video played in sync, like this. Some TV channels would fill the letterbox with their network ID, like this. A fad popularised by Hype Williams in the 2000s was where certain music videos such as Beyoncé's "Check On It" and Ne-Yo's "So Sick" employed video backgrounds on the top and bottom bars, which amounted to a visually impressive eye candy back when most households who watched MTV had a 4:3 CRT television, making full use of the negative space left by the use of widescreen footage. Williams' letterbox effect was so popular that he had to abandon that style as it went "beyond being flattering."
Some movies, particularly older ones, came to VHS with letterboxing employed only on the opening and ending credits, since presenting those sequences in Pan and Scan would have resulted in some actors' or crew members' names becoming obscured from the viewers. The studios occasionally tried to make the shift less distracting by replacing the black bars with patterns similar to the background of the Artistic Title or the Creative Closing Credits.
Although letterboxing preserves the entirety of the picture as it was shot, that picture is much smaller than a pan and scan transfer, which can be somewhat disconcerting on smaller television sets. Further, some viewers claim to be distracted by the empty black bars on the screen, preferring that the screen be filled with picture. Again, modern wide-screened TV sets help diminish this problem somewhat, although films shot in even wider formats (such as vintage CinemaScope, Todd-AO, Ultra Panavision 70, and Cinerama releases from the 1950s and '60s) are usually letterboxed rather than cropped even in the "widescreen" home video releases.
Although there was some consumer resistance to the format in the early years, it has now become virtually the norm for home video, and to wish for pan and scan instead is the mark of a rube dumb enough to spend the same amount of money for up to 33% less picture. Many newer movies released on home video actually make use of that dead space, having captions and subtitles appear in the black bars rather than within the frame itself. Even without such considerations, there are a number of commercials and TV shows that are formatted for letterbox presentation because it gives them a classy look like a big-budget feature film (most movies are shot in 21:9, and so we associate things shot in that aspect ratio to be all movie-like).
Now to get really fancy: When this is done horizontally (that is, an image is shown on a wider screen with black space at the sides), it is known as "pillarboxing", after a type of upright mailbox used in England. And "windowboxing" occurs when an already-letterboxed image is pillarboxed, or vice versa, forming a black "picture frame" around the image. There's even a "smilebox" format for certain Cinerama titles, which simulates the curvature of the screen with concave lines at the top and bottom of the image.
It gets wilder when some films are shot in 4:3 knowing that they'll be exhibited in 16:9; movie projectors have a scrim that blocks the upper and lower parts of the frame. A film that is shot in this manner has two basic options: 1) Simply make sure that nothing plot-relevant ends up in that dead space that will be blocked off, or 2) Make use of that space for lighting rigs or other equipment that will simply be obscured. The latter becomes a problem if said film is shown in 4:3 on television without the aforementioned scrims, because some of the effects are spoiled; for example, Pee-wee's Big Adventure infamously has the "bike chain" visual gag showing the container with a false bottom, Blood Waters of Dr. Z with the fish creature's visible sneakers, or 12 to the Moon with the visible lighting rigs on the "moonscape". Some films like Moonstruck are shot in 4:3 knowing they'll be in letterbox on the screen and 4:3 on television, meaning that in terms of not losing any part of the image the 4:3 version is actually superior and no Pan and Scan is needed (as long as they go for option 1).
Turner Classic Movies did an excellent explanation of the difference between Letterboxing and Pan And Scan.