C# Signature:

[DllImport("advapi32")]
public static extern IntPtr CreateService(    
            IntPtr                hSCManager,
            string                lpServiceName,
            string                lpDisplayName,
            SC_MANAGER_ACCESS    dwDesiredAccess,
            SC_SERVICE_TYPE        dwServiceType,
            SC_START_TYPE        dwStartType,
            SC_ERROR_CONTROL    dwErrorControl,
            string                lpBinaryPathName,    // Make sure to double quote, and double escape
            string                lpLoadOrderGroup,    // Use null for no group
            IntPtr                lpdwTagId,    // Use null for no tag
            string                lpDependencies,    // Use null for no dependencies
            string                lpServiceStartName, // Use DOMAIN\USER
            string                lpPassword
            );

VB Signature:

    <DllImport("advapi32.dll", CharSet:=CharSet.Auto, SetLastError:=True)> _
    Private Shared Function CreateService(ByVal hSCManager As IntPtr, ByVal serviceName As String, _
                ByVal displayName As String, ByVal desiredAccess As Int32, ByVal serviceType As Int32, _
                ByVal startType As Int32, ByVal errorcontrol As Int32, ByVal binaryPathName As String, _
                ByVal loadOrderGroup As String, ByVal TagBY As Int32, ByVal dependencides As String, _
                ByVal serviceStartName As String, ByVal password As String) As IntPtr

User-Defined Types:

[Flags]
public enum SC_MANAGER_ACCESS : int
{
    CONNECT         = 0x0001,
    CREATE_SERVICE      = 0x0002,
    ENUMERATE_SERVICE   = 0x0004,
    LOCK        = 0x0008,
    QUERY_LOCK_STATUS   = 0x0010,
    MODIFY_BOOT_CONFIG  = 0x0020,

    ALL_ACCESS      =    // STANDARD_RIGHTS_REQUIRED      |
                CONNECT        |
                CREATE_SERVICE     |
                ENUMERATE_SERVICE  |
                LOCK           |
                QUERY_LOCK_STATUS  |
                MODIFY_BOOT_CONFIG
}

[Flags]
public enum SC_SERVICE_TYPE : int
{
    KERNEL_DRIVER      = 0x00000001,
    FILE_SYSTEM_DRIVER     = 0x00000002,
    ADAPTER        = 0x00000004,
    RECOGNIZER_DRIVER      = 0x00000008,

    DRIVER         = (KERNEL_DRIVER |
                FILE_SYSTEM_DRIVER |
                RECOGNIZER_DRIVER) ,

    WIN32_OWN_PROCESS      = 0x00000010,
    WIN32_SHARE_PROCESS    = 0x00000020,
    WIN32          =(WIN32_OWN_PROCESS |
                WIN32_SHARE_PROCESS),

    INTERACTIVE_PROCESS    = 0x00000100,

    TYPE_ALL           = (    WIN32  |
                ADAPTER |
                DRIVER  |
                INTERACTIVE_PROCESS)
}

public enum SC_START_TYPE : int
{
    SERVICE_BOOT_START        = 0x00000000,
    SERVICE_SYSTEM_START      = 0x00000001,
    SERVICE_AUTO_START        = 0x00000002,
    SERVICE_DEMAND_START      = 0x00000003,
    SERVICE_DISABLED          = 0x00000004
}

public enum SC_ERROR_CONTROL : int
{
    SERVICE_ERROR_IGNORE       = 0x00000000,
    SERVICE_ERROR_NORMAL       = 0x00000001,
    SERVICE_ERROR_SEVERE       = 0x00000002,
    SERVICE_ERROR_CRITICAL     = 0x00000003
}

Notes:

The 4th parameter from the end, TagBY, should - accordig to the API documention, be a ByRef parameter. Unfortunatly, the call only works if the parameter is ByVal.

Tips & Tricks:

Please add some!

Sample Code:

Dim scHandle As IntPtr = OpenSCManager(Nothing, Nothing, SC_MANAGER_ALL_ACCESS)
    Dim serviceName As String = "AAATestService"
    Dim displayName As String = "AAATestDisplayName"

    If OpenFileDialog1.ShowDialog() <> DialogResult.OK Then
        MsgBox("aborting")
    End If

    Dim pathName As String = Chr(34) & OpenFileDialog1.FileName & Chr(34)

    Dim serviceHandle As IntPtr = CreateService(scHandle, serviceName, displayName, SERVICE_ALL_ACCESS, SERVICE_WIN32_OWN_PROCESS, _
                SERVICE_AUTO_START, SERVICE_ERROR_NORMAL, pathName, Nothing, 0, Nothing, Nothing, Nothing)
    If serviceHandle.Equals(IntPtr.Zero) Then
        MsgBox(Marshal.GetLastWin32Error())
    End If

    CloseServiceHandle(serviceHandle)
    CloseHandle(scHandle)

Alternative Managed API:

System.ServiceProcess.ServiceInstaller - http://msdn.microsoft.com/library/en-us/cpref/html/frlrfSystemServiceProcessServiceInstallerClassTopic.asp