One of the cool features of Visual Studio 2008 and .NET 3.5 is the introduction of the SendActivity and ReceiveActivity, which provides a marriage of WCF and WF. Guy Berstein has a great overview of some of the new WF and WCF features. This makes creating services much simpler through the use of workflow and visual designers.
In Visual Studio 2008, just choose File / New / Project / WCF / Sequential Workflow Service Library. The result is a library that contains your workflow definition. Most of the examples that you see on this will use the really cool new WorkflowServiceHost. But how do you host this library, but it's not evident how to host this using IIS. It's pretty easy, actually. Just add a reference from your WCF service project and edit the .svc file. Remove the CodeBehind attribute, point the Service attribute to your library, and add a Factory attribute to use the WorkflowServiceHost.
<%@ ServiceHost Factory="System.ServiceModel.Activation.WorkflowServiceHostFactory" Language="C#" Debug="true" Service="WFServiceLibrary2.Workflow1" %>
[Update: D'oh! Forgot to give credit to the infamous Jon Flanders for showing me how to do this.]