Programming to an interface means that you should focus on what the code does, not how it is actually implemented. See Telastyn's answer to Understanding “programming to an interface”. Interface classes help to enforce this guideline, but this does not mean that you should never use concrete classes.
I really like the zip code example:
In 1963, the United States Postal Service introduces zip codes that consist of five digits. You may now get the (bad) idea that an integer is a sufficient representation and use it throughout your code. 1983, a new zip code format is introduced. It uses 5 digits, a hyphen, and 4 other digits. Suddenly, zip codes are not integers anymore and you need to change all places that use integers for zip codes to something else, for example, to strings. This refactoring could have been avoided, if a designated ZipCode class would have been used. Then, only the internal representation of the ZipCode class needed to be changed and its usages would have stayed the same.
Using a ZipCode class is already programming to an interface: Instead of programming against some concrete implementation ("integer" / "string"), you program against some abstraction ("zip code").
If necessary, you can add another level of abstraction: You may need to support different postal code formats for different countries. For example, you could add an interface IPostalCode with implementations like PostalCodeUS (which is just the ZipCode from above), PostalCodeIreland, PostalCodeNetherlands etc. However, too many levels of abstraction can also make the code more complex and harder to reason about and I think it depends on your application's requirements whether you want to use some ZipCode class or some IPostalCode interface. Maybe a ZipCode that internally uses a (unicode) string is good enough for all countries and country specific stuff, for example, validation, can be handled outside the class in some PostalCodeValidator / IPostalCodeValidator.
