From the Official Rules of Major League Baseball, section 10.17, "STRIKEOUTS":
A strikeout shall be scored whenever:
(1) A batter is put out by a third strike caught by the catcher;
(2) A batter is put out by a third strike not caught when there is a runner on first before two are out;
(3) A batter becomes a runner because a third strike is not caught;
(4) A batter bunts foul on third strike. EXCEPTION: If such bunt on third strike results in a foul fly caught by any fielder, do not score a strikeout. Credit the fielder who catches such foul fly with a putout.
Also referred to as a whiff, especially when the batter strikes out by swinging and missing for a third strike, or a punch-out, especially when the batter strikes out looking at the third strike without swinging at it.
When a pitcher strikes a batter out he may be said to have fanned or rung up the batter.
The official scorer "awards" both the pitcher and the batter with a strikeout, abbreviated in the statistics as "K". In some scoring systems a batter striking out looking is recorded using a backwards K to distinguish it from a swinging strikeout.
At Fenway Park where Pedro Martinez pitches, and occasionally at other parks where strikeout pitchers like Roger Clemens or Randy Johnson play, a group of fans near an outfield wall will organize to bring and hang "K" signs to represent each strikeout the pitcher records during the game. When a pitcher has notched upwards of a dozen strikeouts the resulting wall of Ks can look quite impressive.
In some parks the team or a radio station in need of advertising may distribute handheld paper "fans" for fans to wave when their pitcher "fans" a batter. That's not nearly as cool.
If the first two batters to strike out go down swinging, the fans hanging up "K" signs often choose to mark the third strikeout with a backwards K, even if the third is also a swinging strikeout. When the fourth is recorded, the third is switched back. This is to avoid creating the unfortunate impression that the fans are promoting the KKK.
The major league record for strikeouts by a single pitcher in a nine-inning game is twenty, first set by Roger Clemens in 1986 for the Boston Red Sox. Clemens remarkably equalled the feat in 1996, and Kerry Wood of the Chicago Cubs did it again in 1998.
The single-season record for strikeouts is held by Nolan Ryan, who notched 383 in 1973 for the California (now Anaheim) Angels. Ryan also holds the career record with 5,714, well ahead of Steve Carlton with 4136 and Clemens with 3991. Ryan pitched for 27 years, frequently pitching in a large number of games each year. in 1973 he made 41 appearances. In 26 of those appearances, he pitched a complete game. You might think, then, that he got a lot of strikeouts just because he pitched a lot. That's not the case. Pitching in a lot of innings certainly helped him rack up the Ks, but Ryan recorded them at a rate of 9.55 strikeouts per nine innings (or "K/9") for his career. All-time, that's second only to the still-active Randy Johnson, who currently sits with an outrageous 11.55.
Strikeouts are one of the few defense-independent pitching statistics. They come purely out of the interaction between the pitcher and the batter. Walks and home runs allowed are other such stats. Earned-run average, hits allowed, and wins, are not. See Voros McCracken for more information about which statistics represent the skill of the pitcher, and which are just luck.