One stumbles upon this phrase when reading about design patterns.

But I don't understand it, could someone explain this for me?

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
}