Here's what has worked for me.
From an infrastructure stand point you will need to have 2 Windows servers that are clustered. (2 standard Windows Server boxes will do, the Clustering piece can be installed and configured, most sys admins should know how to do this.) Next, install your service on both nodes of the cluster and have them both turned OFF and set to MANUAL startup. Next, add a clustered resource to the Windows Cluster Administrator for your service that will manage turning on and off your service on whichever node is active. Let the Windows cluster manage when your service is running and on which node. This is the easy part of clustering your service.
From the service stand point, you will want to design your service so that it can be as stateless as possible. This is kind of lame advice but it really depends on what your service is doing. In the design, just assume that at somepoint during the code's lifetime it will stop at the worst possible time. How will the service on the node2 know where to pickup where node1 left off? That's the hard part that you need to design for. Depending on what your service is doing you can leave the last completed task in a db table or shared data file. You could also have it start from the beginning and double check whether that task has been completed or not before acting upon it.
Again, it is really going to depend on what the service needs to accomplish. Hope this helps.