What do programmers mean when they say, "Code against an interface, not an object."?

Consider:

class MyClass
{
    //Implementation
    public void Foo() {}
}

class SomethingYouWantToTest
{
    public bool MyMethod(MyClass c)
    {
        //Code you want to test
        c.Foo();
    }
}

Because MyMethod accepts only a MyClass, if you want to replace MyClass with a mock object in order to unit test, you can't. Better is to use an interface:

interface IMyClass
{
    void Foo();
}

class MyClass : IMyClass
{
    //Implementation
    public void Foo() {}
}

class SomethingYouWantToTest
{
    public bool MyMethod(IMyClass c)
    {
        //Code you want to test
        c.Foo();
    }
}

Now you can test MyMethod, because it uses only an interface, not a particular concrete implementation. Then you can implement that interface to create any kind of mock or fake that you want for test purposes. There are even libraries like Rhino Mocks' Rhino.Mocks.MockRepository.StrictMock<T>(), which take any interface and build you a mock object on the fly.

It's all a matter of intimacy. If you code to an implementation (a realized object) you are in a pretty intimate relationship with that "other" code, as a consumer of it. It means you have to know how to construct it (ie, what dependencies it has, possibly as constructor params, possibly as setters), when to dispose of it, and you probably can't do much without it.

An interface in front of the realized object lets you do a few things -

1. For one you can/should leverage a factory to construct instances of the object. IOC containers do this very well for you, or you can make your own. With construction duties outside of your responsibility, your code can just assume it is getting what it needs. On the other side of the factory wall, you can either construct real instances, or mock instances of the class. In production you would use real of course, but for testing, you may want to create stubbed or dynamically mocked instances to test various system states without having to run the system.
2. You don't have to know where the object is. This is useful in distributed systems where the object you want to talk to may or may not be local to your process or even system. If you ever programmed Java RMI or old skool EJB you know the routine of "talking to the interface" that was hiding a proxy that did the remote networking and marshalling duties that your client didn't have to care about. WCF has a similar philosophy of "talk to the interface" and let the system determine how to communicate with the target object/service.

** UPDATE ** There was a request for an example of an IOC Container (Factory). There are many out there for pretty much all platforms, but at their core they work like this:

1. You initialize the container on your applications startup routine. Some frameworks do this via config files or code or both.

2. You "Register" the implementations that you want the container to create for you as a factory for the interfaces they implement (eg: register MyServiceImpl for the Service interface). During this registration process there is typically some behavioral policy you can provide such as if a new instance is created each time or a single(ton) instance is used

3. When the container creates objects for you, it injects any dependencies into those objects as part of the creation process (ie, if your object depends on another interface, an implementation of that interface is in turn provided and so on).

Pseudo-codishly it could look like this:

IocContainer container = new IocContainer();

//Register my impl for the Service Interface, with a Singleton policy
container.RegisterType(Service, ServiceImpl, LifecyclePolicy.SINGLETON);

//Use the container as a factory
Service myService = container.Resolve<Service>();

//Blissfully unaware of the implementation, call the service method.
myService.DoGoodWork();

When programming against an interface you will write code that uses an instance of an interface, not a concrete type. For instance you might use the following pattern, which incorporates constructor injection. Constructor injection and other parts of inversion of control aren't required to be able to program against interfaces, however since you're coming from the TDD and IoC perspective I've wired it up this way to give you some context you're hopefully familiar with.

public class PersonService
{
    private readonly IPersonRepository repository;

    public PersonService(IPersonRepository repository)
    {
        this.repository = repository;
    }

    public IList<Person> PeopleOverEighteen
    {
        get
        {
            return (from e in repository.Entities where e.Age > 18 select e).ToList();
        }
    }
}

The repository object is passed in and is an interface type. The benefit of passing in an interface is the ability to 'swap out' the concrete implementation without changing the usage.

For instance one would assume that at runtime the IoC container will inject a repository that is wired to hit the database. During testing time, you can pass in a mock or stub repository to exercise your PeopleOverEighteen method.