En teoría de programación orientada a objetos, donde todo es un objeto y los objetos se comunican entre sí a través de mensajes.
La interfaz son los mensajes que sabe responder un objeto (también se lo conoce como protocolo).
En un lenguaje orientado a objetos puro basado en clases, la interfaz está dada por la/s clase/s a las que pertenece el objeto.
En un lenguaje orientado a objetos puro basado en prototipos, no queda otra que analizar el objeto en sí para saber que mensajes acepta.
En lenguajes como Java o C#, las construcciones del tipo Interface, siguen está idea, es decir definen que métodos (mensajes) debe responder una clase que la implementen (la interfaz) y son un mecanismo para tratar con la herencia multiple.
Para ejemplos de interfaz mira la respuesta de fredyfx
.
Referencia: Notas de Alan Kay sobre la definición de orientado a objetos.
Alan Kay es el padre de Smalltalk, considerado el primer lenguaje de programación orientado a objetos.