A very nasty type of patent, where the patent owner hides the fact that he has a patent on something obvious, waits for the idea to become commonly used, then starts asking for royalties and fees.

The canonical example of a submarine patent is Unisys' patent on LZW (Lempel-Ziv-Welch) compression. They had it since the early 1980's. Compuserve then used LZW in its graphics format (which just happened to become the popular GIF format). GIFs then became popular on the Web; all the time Unisys hiding this patent. Then recently, Unisys comes out of the woodwork, says that the GIF format uses patented LZW technology and demands every Web site pay it a US$5000 licensing fee.

British Telecom recently claimed that they had a patent on hyperlinking (i.e. you click on underlined text and it takes you somewhere else). They want to charge licensing fees ... this would also be a submarine patent.

In some states and countries, they've introduced laws to prevent submarine patents, which means that if you want to maintain a patent, you have to enforce patents from the beginning of your patent being granted until it expires. This has a nasty side effect though, as it sometimes gets in the way, for example, of open source projects, since the companies with the patents can't just give the patents away or they would be risking losing the patent.