I don't have a complete write up yet for people trying to learn how this works, but I now have a write up for how to at least accomplish this goal.
http://thehappypath.net/2011/11/21/using-msdeploy-for-windows-services/
(edit: link is dead for now.  Let me know if you're interested and I can post it elsewhere).
My guide goes through these overall steps:
- Ensure the service starts itself upon installation (not crucial, but easier to deal with)
- Add the Microsoft.WebApplication.targets file to your project, even though you don't have a web project.  This enables the PackageMsBuild target.
- Add a custom .targets file to your project that builds a custom MsBuild package manifest
- Add some batch scripts to your project to stop/uninstall and install the service
- Add a Parameters.xml file to support changing the target deployment directory a bit more easily
- Set up app.config transformations using the SlowCheetah Visual Studio addon
Then you can package your project with this command line:
msbuild MyProject.csproj /t:Package /p:Configuration=Debug
You can deploy the resulting package with this command line:
MyService.Deploy.cmd /Y /M:mywebserver -allowUntrusted
The most undocumented part of this (except for my guide) is creating the custom manifest.  Here's a dump of my current file (note, it is still a bit buggy, but can be fixed - See this question: MsDeploy remoting executing manifest twice - and try to keep to using only direct batch files for runCommand).
<?xml version="1.0" encoding="utf-8"?>
<Project ToolsVersion="4.0" DefaultTargets="Build"
         xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
  <!-- This file must be included before Microsoft.Web.Publishing.targets so we can hook into BeforeAddIisSettingAndFileContentsToSourceManifest -->
  <PropertyGroup>
    <!-- Include our targets -->
    <IncludeStopServiceCommand>True</IncludeStopServiceCommand>
    <IncludeSetCustomAclsProvider>True</IncludeSetCustomAclsProvider>
    <IncludeInstallServiceCommand>True</IncludeInstallServiceCommand>
    <IncludeMoveAppConfigToCorrectPackagePath>True</IncludeMoveAppConfigToCorrectPackagePath>
    <!-- Uncomment to enable more verbose MsBuild logging -->
    <!-- <EnablePackageProcessLoggingAndAssert>True</EnablePackageProcessLoggingAndAssert> -->
    <!-- Enable web.config transform, but hack it to work for app.config -->
    <ProjectConfigFileName>app.config</ProjectConfigFileName>
    <TransformWebConfigEnabled>True</TransformWebConfigEnabled>
    <UseParameterizeToTransformWebConfig>True</UseParameterizeToTransformWebConfig>
    <!-- Enable web project packaging, but hack it to work for non-web app -->
    <DeployAsIisApp>False</DeployAsIisApp>
    <IncludeIisSettingsOnPublish>False</IncludeIisSettingsOnPublish>
    <IncludeSetAclProviderOnDestination>False</IncludeSetAclProviderOnDestination>
    <DisableAllVSGeneratedMSDeployParameter>True</DisableAllVSGeneratedMSDeployParameter>
    <!-- Insert our custom targets into correct places in build process -->
    <BeforeAddIisSettingAndFileContentsToSourceManifest Condition="'$(BeforeAddIisSettingAndFileContentsToSourceManifest)'==''">
      $(BeforeAddIisSettingAndFileContentsToSourceManifest);
      AddStopServiceCommand;
    </BeforeAddIisSettingAndFileContentsToSourceManifest>
    <AfterAddIisSettingAndFileContentsToSourceManifest Condition="'$(AfterAddIisSettingAndFileContentsToSourceManifest)'==''">
      $(AfterAddIisSettingAndFileContentsToSourceManifest);
      AddSetCustomAclsProvider;
      AddInstallServiceCommand;
    </AfterAddIisSettingAndFileContentsToSourceManifest>
    <OnAfterCopyAllFilesToSingleFolderForPackage Condition="'$(OnAfterCopyAllFilesToSingleFolderForPackage)'==''">
      $(OnAfterCopyAllFilesToSingleFolderForPackage);
      MoveAppConfigToCorrectPackagePath;
    </OnAfterCopyAllFilesToSingleFolderForPackage>
  </PropertyGroup>
  <!-- Custom targets -->
  <Target Name="AddStopServiceCommand" Condition="'$(IncludeStopServiceCommand)'=='true'">
    <Message Text="Adding runCommand to stop the running Service" />
    <ItemGroup>
      <MsDeploySourceManifest Include="runCommand">
        <path>$(_MSDeployDirPath_FullPath)\bin\servicestop.bat</path>
        <waitInterval>20000</waitInterval>
        <AdditionalProviderSettings>waitInterval</AdditionalProviderSettings>
      </MsDeploySourceManifest>
    </ItemGroup>
  </Target>
  <Target Name="AddSetCustomAclsProvider" Condition="'$(IncludeSetCustomAclsProvider)'=='true'">
    <ItemGroup>
      <MsDeploySourceManifest Include="setAcl">
        <Path>$(_MSDeployDirPath_FullPath)</Path>
        <setAclUser>LocalService</setAclUser>
        <setAclAccess>FullControl</setAclAccess> <!-- Todo: Reduce these permissions -->
        <setAclResourceType>Directory</setAclResourceType>
        <AdditionalProviderSettings>setAclUser;setAclAccess;setAclResourceType</AdditionalProviderSettings>
      </MsDeploySourceManifest>
    </ItemGroup>
  </Target>
  <Target Name="AddInstallServiceCommand" Condition="'$(IncludeInstallServiceCommand)'=='true'">
    <Message Text="Adding runCommand to install the Service" />
    <ItemGroup>
      <MsDeploySourceManifest Include="runCommand">
        <path>cmd.exe /c $(_MSDeployDirPath_FullPath)\bin\serviceinstall.bat</path>
        <waitInterval>20000</waitInterval>
        <dontUseCommandExe>false</dontUseCommandExe>
        <AdditionalProviderSettings>waitInterval;dontUseCommandExe</AdditionalProviderSettings>
      </MsDeploySourceManifest>
    </ItemGroup>
  </Target>
  <Target Name="MoveAppConfigToCorrectPackagePath"
          Condition="'$(IncludeMoveAppConfigToCorrectPackagePath)'=='true'">
    <PropertyGroup>
      <OriginalAppConfigFilename>$(_PackageTempDir)\App.Config</OriginalAppConfigFilename>
      <TargetAppConfigFilename>$(_PackageTempDir)\bin\$(TargetFileName).config</TargetAppConfigFilename>
    </PropertyGroup>
    <Copy SourceFiles="$(OriginalAppConfigFilename)" DestinationFiles="$(TargetAppConfigFilename)" 
          Condition="Exists($(OriginalAppConfigFilename))" />
    <Delete Files="$(OriginalAppConfigFilename)" 
            Condition="Exists($(OriginalAppConfigFilename))" />
  </Target>
</Project>