I recently deployed a SharePoint extranet using Microsoft Office Search Server Express 2008 (MSSX), which turned out to be quite interesting.  I will share all the salient details of that adventure in my next post.  But first: 

1. Using Windows CALs for the anticipated number of users.
2. Using the External Connector license (this is the same type of license that would cover an internet-facing Terminal Server).
1. The External Connector costs $2000 per server.  (Interestingly, an EC license for Terminal Server costs $8000.) 
3. Using Windows 2003/2008 Web Edition, which does not require CALs or an EC license, but can’t host a SQL instance.  There are some strict limitations to using Windows Web Edition and most IT folks avoid it because it can limit flexibility, but it’s a cost effective solution, and it does cost less than Standard Edition.

Note: Actually, I have conflicting information on this.  On this page it says that Windows 2003 Web Edition will allow you to install SQL 2005 Express Edition; however, this may only pertain to the R2 edition of Windows 2003.  I've tried to install SQL Express on Web Edition in the past, and it wouldn't let me, but that was before R2.  Maybe someone could confirm this?Updated 10/24/08: Bill Staples of Microsoft confirms here that Windows Web Server 2008 allows for a local install of SQL Server.

References:

• Office & SharePoint Pro: License to Fill: Licensing WSS for the Extranet
• Office & SharePoint Pro: Licensing WSS
• Windows IT Pro: Using SharePoint for Extranets
• WSS Collutions: About Licensing 
• Microsoft: Pricing for Windows 2003 R2 Editions
•  Microsoft: External Connector Licensing
• Microsoft: Windows 2003 Web Edition Licensing
• Microsoft: Pricing for MOSS Editions
• Microsoft: MOSS FAQ 

• (Updated 9/26/08): Mike Walsh asked that I be a little clearer in my wording, so I will clarify:
• The WSS Collutions article I linked to was written in 2003 for the 2.0 version of WSS.  He actually updated this article after I linked to it, so if you read it yesterday you might want to go back and take another look.  
• There is no license covering WSS specifically.  You are licensing the connection to Windows.
• The important thing to remember is that Microsoft is concerned about authenticated access to the server.  
• Mike Walsh makes a good point: "Licensing is as always something that should be checked with Microsoft."  
• Anonymous users do not require licensing.  Mike seems to be saying that even if you are only serving anonymous users, you will still need an External Connector license.  Although my original assumption came from reading the SharePoint FAQ (text is below), I will follow the MVP's guidance on this one. 
• Another useful link is a terse "Supplemental" statement from Microsoft about licensing and WSS:
• Windows SharePoint Services conforms to the Windows Server 2003 licensing model.
• The usage of the Windows SharePoint Services on Windows Server 2003 Web Edition, is limited to front-end Web serving tasks. The data storage portion of Windows SharePoint Services may not be installed or used on Windows Server 2003 Web Edition.
• The External Connector is different from the edition of MOSS called Microsoft Office SharePoint Server 2007 for Internet Sites, which is essentially MOSS 2007 Enterprise with a blanket license covering unlimited connections. 
• From the MOSS FAQ:
• If I am using forms authentication or any other third-party authenticationsystem with external users, do I still need to purchase Windows Server 2003External Connector (EC) license? 
• Yes. External users that are authenticated, by any means, would requireeither a Windows CAL or a server with an External Connector license.
• If I am using SharePoint for an Internet facing website do I still need topurchase Client Access Licenses ("CALs")?  
• If you are creating an Internet- or Extranet-facing website, it isrecommended that you use Microsoft Office SharePoint Server 2007 forInternet sites. This license does not require the purchase of Client AccessLicenses. However, all content, information, and applications on thehosted using an "Internet Sites" edition cannot be accessed by employeescreating, sharing, or collaborating on content which is solely for internaluse only, such as an intranet portal scenario.