What does "program to interfaces, not implementations" mean?

Think of an interface as a contract between an object and its clients. That is the interface specifies the things that an object can do, and the signatures for accessing those things.

Implementations are the actual behaviours. Say for example you have a method sort(). You can implement QuickSort or MergeSort. That should not matter to the client code calling sort as long as the interface does not change.

Libraries like the Java API and the .NET Framework make heavy use of interfaces because millions of programmers use the objects provided. The creators of these libraries have to be very careful that they do not change the interface to the classes in these libraries because it will affect all programmers using the library. On the other hand they can change the implementation as much as they like.

If, as a programmer, you code against the implementation then as soon as it changes your code stops working. So think of the benefits of the interface this way:

1. it hides the things you do not need to know making the object simpler to use.
2. it provides the contract of how the object will behave so you can depend on that

Interfaces are just contracts or signatures and they don't know anything about implementations.

Coding against interface means, the client code always holds an Interface object which is supplied by a factory. Any instance returned by the factory would be of type Interface which any factory candidate class must have implemented. This way the client program is not worried about implementation and the interface signature determines what all operations can be done. This can be used to change the behavior of a program at run-time. It also helps you to write far better programs from the maintenance point of view.

Here's a basic example for you.

public enum Language
{
    English, German, Spanish
}

public class SpeakerFactory
{
    public static ISpeaker CreateSpeaker(Language language)
    {
        switch (language)
        {
            case Language.English:
                return new EnglishSpeaker();
            case Language.German:
                return new GermanSpeaker();
            case Language.Spanish:
                return new SpanishSpeaker();
            default:
                throw new ApplicationException("No speaker can speak such language");
        }
    }
}

[STAThread]
static void Main()
{
    //This is your client code.
    ISpeaker speaker = SpeakerFactory.CreateSpeaker(Language.English);
    speaker.Speak();
    Console.ReadLine();
}

public interface ISpeaker
{
    void Speak();
}

public class EnglishSpeaker : ISpeaker
{
    public EnglishSpeaker() { }

    #region ISpeaker Members

    public void Speak()
    {
        Console.WriteLine("I speak English.");
    }

    #endregion
}

public class GermanSpeaker : ISpeaker
{
    public GermanSpeaker() { }

    #region ISpeaker Members

    public void Speak()
    {
        Console.WriteLine("I speak German.");
    }

    #endregion
}

public class SpanishSpeaker : ISpeaker
{
    public SpanishSpeaker() { }

    #region ISpeaker Members

    public void Speak()
    {
        Console.WriteLine("I speak Spanish.");
    }

    #endregion
}

This is just a basic example and actual explanation of the principle is beyond the scope of this answer.

EDIT

I have updated the example above and added an abstract Speaker base class. In this update, I added a feature to all Speakers to "SayHello". All speaker speak "Hello World". So that's a common feature with similar function. Refer to the class diagram and you'll find that Speaker abstract class implement ISpeaker interface and marks the Speak() as abstract which means that the each Speaker implementation is responsible for implementing the Speak() method since it varies from Speaker to Speaker. But all speaker say "Hello" unanimously. So in the abstract Speaker class we define a method that says "Hello World" and each Speaker implementation will derive the SayHello() method.

Consider a case where SpanishSpeaker cannot Say Hello so in that case you can override the SayHello() method for Spanish Speaker and raise proper exception.

Please note that, we have not made any changes to Interface ISpeaker. And the client code and SpeakerFactory also remain unaffected unchanged. And this is what we achieve by Programming-to-Interface.

And we could achieve this behavior by simply adding a base abstract class Speaker and some minor modification in Each implementation thus leaving the original program unchanged. This is a desired feature of any application and it makes your application easily maintainable.

public enum Language
{
    English, German, Spanish
}

public class SpeakerFactory
{
    public static ISpeaker CreateSpeaker(Language language)
    {
        switch (language)
        {
            case Language.English:
                return new EnglishSpeaker();
            case Language.German:
                return new GermanSpeaker();
            case Language.Spanish:
                return new SpanishSpeaker();
            default:
                throw new ApplicationException("No speaker can speak such language");
        }
    }
}

class Program
{
    [STAThread]
    static void Main()
    {
        //This is your client code.
        ISpeaker speaker = SpeakerFactory.CreateSpeaker(Language.English);
        speaker.Speak();
        Console.ReadLine();
    }
}

public interface ISpeaker
{
    void Speak();
}

public abstract class Speaker : ISpeaker
{

    #region ISpeaker Members

    public abstract void Speak();

    public virtual void SayHello()
    {
        Console.WriteLine("Hello world.");
    }

    #endregion
}

public class EnglishSpeaker : Speaker
{
    public EnglishSpeaker() { }

    #region ISpeaker Members

    public override void Speak()
    {
        this.SayHello();
        Console.WriteLine("I speak English.");
    }

    #endregion
}

public class GermanSpeaker : Speaker
{
    public GermanSpeaker() { }

    #region ISpeaker Members

    public override void Speak()
    {
        Console.WriteLine("I speak German.");
        this.SayHello();
    }

    #endregion
}

public class SpanishSpeaker : Speaker
{
    public SpanishSpeaker() { }

    #region ISpeaker Members

    public override void Speak()
    {
        Console.WriteLine("I speak Spanish.");
    }

    public override void SayHello()
    {
        throw new ApplicationException("I cannot say Hello World.");
    }

    #endregion
}