In any event, they have never enforced it against a web site for having GIF on the page, and it is highly unlikely they ever will even if it is possible (bad karma...the backlash would be too severe from a public relations standpoint). They require licensing fees from makers of programs that can save in gif format (eg Photoshop).

This patent issue was one of the motivations behind the open source PNG format. As browsers add full support for PNG (IE and NS4 plus support it to some extent, NS6.1 has more complete support, don't know if IE6 has improved support or not), and more imaging programs add that as a file format option, you will see more migration to PNG over GIF...PNG images are better for the web anyway. In the meantime, don't worry about it.

Note that PNG is not meant to be substitute for JPG and should not be used for high color/photo type graphics.
Info on PNG: http://www.libpng.org/pub/png/

"According to Mark Starr, General Patent and Technology Counsel for Unisys, if the GIFs on your Web site were created with software that is licensed by Unisys, you are fine. And, Starr added, virtually all of the major, heavily-used, commercial graphics programs from what he calls "reputable companies" (e.g. Adobe, Corel, JASC, Macromedia, Microsoft, AOL/Netscape, etc.) are licensed by Unisys. He said that even the "included" software packaged with most scanners and digital cameras is licensed. Use it, create all the GIFs you want with it, post those GIFs to your heart's content, and relax. Unisys will not come after you.

But, if you use GIF graphics created with certain freeware programs, and your chosen program uses LZW compression to create GIFs without a license to use it, you may be violating a Unisys patent. How would Unisys know what software you used to create a particular GIF? Starr says they'll ask you, and, he says, "...assuming we made an inquiry, we would expect a Web site operator to tell us what he used."

(from slashdot.org)

Who would have thought.