A stormy petrel, also known as a storm petrel, is an Atlantic seabird (also found in the Mediterranean). The term "stormy petrel" in general usage has come to refer to a harbinger of trouble; perhaps people believed that the bird was seen just before a storm. Sometime in the late '80s, Elliott Moreton came up with a category of words which can't be used except in the company of specific other words; having heard the word "petrel" only in the company of the word "stormy," he decided to call such items "stormy petrels." As it happens, there is such a thing as a petrel which isn't stormy, but the term was a catchy one so it stuck.
[Note added in 2018: There’s more information and a clearer description in the reader comments page.]
Some examples are in order at this point: The word "shrift" never occurs except when modified by "short"; in Elliott's phrasing, "All SHRIFT is SHORT." You can't refer to "low dudgeon" or "red dudgeon" or just plain "dudgeon" by itself; all DUDGEON is HIGH. You can't "wend a book" or "wend around" or just "wend"; the only thing you can WEND is your WAY. You can't "bestride carefully" or "bestride through the clouds"; the only way you can BESTRIDE is LIKE A COLOSSUS. And so on.
Note that "can't" above doesn't mean such usage would be ungrammatical; it's just that people never do use a stormy petrel without its associated word or phrase. As a joke someone could refer to "long shrift" or "low dudgeon," but such usage would be obviously a joke. Also, a stormy petrel is not just a fixed phrase: for instance, "He ran like the wind" is such a common phrase it's a cliché, but none of its constituents are stormy petrels.
Someone once defined a stormy petrel as a phrase in which you can hear part of the phrase and know with certainty what the rest of it is. That's too loose a definition—if you hear "He sashayed [garble] and forth," you know the garbled word must have been "back," but none of the words "back," "forth," or "sashayed" are stormy petrels (because you can use each of them without the others).
We sometimes make a distinction between the rare "strong" stormy petrel, which can never occur without the associated word or phrase, and the more common "weak" stormy petrel, which can never occur as a particular part of speech without the companion word or phrase. For instance, "snub" as an adjective can only modify "nose"; only a NOSE can be SNUB. However, "snub" as a verb can appear in many contexts having nothing to do with noses. Thus, "snub" is a weak stormy petrel, not a strong one.
The complete stormy petrels list, categorized by part of speech, is now available in HTML format. If you have new entries to add, send them to me. And let me know if you think something on the list doesn't belong there.