The primary difference is that Docker as a project is focused on the runtime container only, whereas OpenShift (as a system) includes both the runtime container as well as the REST API, coordination, and web interfaces to deploy and manage individual containers.
Comparing just the runtime containers, OpenShift and Docker both use kernel isolation features to keep tenant processes separate. For Docker that is primarily through LXC and for OpenShift that is largely through SELinux and Multiple Category Security (MCS). Both use cgroups to limit the CPU, memory, and IO of tenants. Upstream OpenShift is looking at LXC to reduce long term effort.
Docker uses AUFS for advanced disk and file copy-on-write sharing, OpenShift neither requires nor is incompatible with such a system.
Inside the container, OpenShift models units of functionality (web servers, dbs) via "cartridges", which are a set of shell script hooks that are called when the system is invoked. The API is described here. A cartridge is roughly similar to a docker image.
Openshift also describes the API by which a broker (coordinator) communicates with nodes (servers that host multiple tenant containers) to invoke endpoints in that container.
EDITED TO ADD: As of June 2015, OpenShift Origin 1.0 runs on top of Docker and Kubernetes, and you can build and develop multi container apps that run on the Docker runtime. OpenShift adds build, image workflow and promotion, and secure container cluster operations on top of Kube and Docker