How do I pass values to the constructor on my wcf service?

You'll need to implement a combination of custom ServiceHostFactory, ServiceHost and IInstanceProvider.

Given a service with this constructor signature:

public MyService(IDependency dep)

Here's an example that can spin up MyService:

public class MyServiceHostFactory : ServiceHostFactory
{
    private readonly IDependency dep;

    public MyServiceHostFactory()
    {
        this.dep = new MyClass();
    }

    protected override ServiceHost CreateServiceHost(Type serviceType,
        Uri[] baseAddresses)
    {
        return new MyServiceHost(this.dep, serviceType, baseAddresses);
    }
}

public class MyServiceHost : ServiceHost
{
    public MyServiceHost(IDependency dep, Type serviceType, params Uri[] baseAddresses)
        : base(serviceType, baseAddresses)
    {
        if (dep == null)
        {
            throw new ArgumentNullException("dep");
        }

        foreach (var cd in this.ImplementedContracts.Values)
        {
            cd.Behaviors.Add(new MyInstanceProvider(dep));
        }
    }
}

public class MyInstanceProvider : IInstanceProvider, IContractBehavior
{
    private readonly IDependency dep;

    public MyInstanceProvider(IDependency dep)
    {
        if (dep == null)
        {
            throw new ArgumentNullException("dep");
        }

        this.dep = dep;
    }

    #region IInstanceProvider Members

    public object GetInstance(InstanceContext instanceContext, Message message)
    {
        return this.GetInstance(instanceContext);
    }

    public object GetInstance(InstanceContext instanceContext)
    {
        return new MyService(this.dep);
    }

    public void ReleaseInstance(InstanceContext instanceContext, object instance)
    {
        var disposable = instance as IDisposable;
        if (disposable != null)
        {
            disposable.Dispose();
        }
    }

    #endregion

    #region IContractBehavior Members

    public void AddBindingParameters(ContractDescription contractDescription, ServiceEndpoint endpoint, BindingParameterCollection bindingParameters)
    {
    }

    public void ApplyClientBehavior(ContractDescription contractDescription, ServiceEndpoint endpoint, ClientRuntime clientRuntime)
    {
    }

    public void ApplyDispatchBehavior(ContractDescription contractDescription, ServiceEndpoint endpoint, DispatchRuntime dispatchRuntime)
    {
        dispatchRuntime.InstanceProvider = this;
    }

    public void Validate(ContractDescription contractDescription, ServiceEndpoint endpoint)
    {
    }

    #endregion
}

Register MyServiceHostFactory in your MyService.svc file, or use MyServiceHost directly in code for self-hosting scenarios.

You can easily generalize this approach, and in fact some DI Containers have already done this for you (cue: Windsor's WCF Facility).

You can simply create and instance of your Service and pass that instance to the ServiceHost object. The only thing you have to do is to add a [ServiceBehaviour] attribute for your service and mark all returned objects with [DataContract] attribute.

Here is a mock up:

namespace Service
{
    [ServiceContract]
    [ServiceBehavior(InstanceContextMode = InstanceContextMode.Single)]
    public class MyService
    {
        private readonly IDependency _dep;

        public MyService(IDependency dep)
        {
            _dep = dep;
        }

        public MyDataObject GetData()
        {
            return _dep.GetData();
        }
    }

    [DataContract]
    public class MyDataObject
    {
        public MyDataObject(string name)
        {
            Name = name;
        }

        public string Name { get; private set; }
    }

    public interface IDependency
    {
        MyDataObject GetData();
    }
}

and the usage:

var dep = new Dependecy();
var myService = new MyService(dep);
var host = new ServiceHost(myService);

host.Open();

I hope this will make life easier for someone.

Mark's answer with the IInstanceProvider is correct.

Instead of using the custom ServiceHostFactory you could also use a custom attribute (say MyInstanceProviderBehaviorAttribute). Derive it from Attribute, make it implement IServiceBehavior and implement the IServiceBehavior.ApplyDispatchBehavior method like

// YourInstanceProvider implements IInstanceProvider
var instanceProvider = new YourInstanceProvider(<yourargs>);

foreach (ChannelDispatcher dispatcher in serviceHostBase.ChannelDispatchers)
{
    foreach (var epDispatcher in dispatcher.Endpoints)
    {
        // this registers your custom IInstanceProvider
        epDispatcher.DispatchRuntime.InstanceProvider = instanceProvider;
    }
}

Then, apply the attribute to your service implementation class

[ServiceBehavior]
[MyInstanceProviderBehavior(<params as you want>)]
public class MyService : IMyContract

The third option: you can also apply a service behavior using the configuration file.