Once upon a time, in a land far, far away, there lived two men by the name of Neal Koblitz and Victor S. Miller. They didn't know each other, however, in 1985 they both suggested using elliptical curves over finite fields for encrypting/decrypting data.
Seriously, though, the following explanation requires that you have a basic understanding of finite fields. Most of it is taken from the Wiki links suggested by D.W.
Elliptic curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields.
Public-key cryptography is based on the intractability of certain mathematical problems. Early public-key systems, such as the RSA algorithm, are secure assuming that it is difficult to factor a large integer composed of two or more large prime factors.
For elliptic-curve-based protocols, it is assumed that finding the discrete logarithm of a random elliptic curve element with respect to a publicly-known base point is infeasible. The size of the elliptic curve determines the difficulty of the problem. It is believed that the same level of security afforded by an RSA-based system with a large modulus can be achieved with a much smaller elliptic curve group. Using a small group reduces storage and transmission requirements.
For current cryptographic purposes, an elliptic curve is a plane curve which consists of the points satisfying the equation
$y^2 = x^3 + ax + b$,
along with a distinguished point at infinity. (The coordinates here are to be chosen from a fixed finite field of characteristic not equal to 2 or 3, or the curve equation will be somewhat more complicated.) This set together with the group operation of the elliptic group theory form an Abelian group, with the point at infinity as identity element. The structure of the group is inherited from the divisor group of the underlying algebraic variety.
How it works depends on the cryptographic scheme you apply it to. As an example, it can be applied it to the Diffie-Hellman key exchange, which is commonly known as the Elliptic Curve Diffie-Hellman (ECDH) key agreement protocol.
Suppose Alice wants to establish a shared key with Bob, but the only channel available for them may be eavesdropped by a third party. Initially, the domain parameters (that is, $(p,a,b,G,n,h)$ in the prime case or $(m,f(x),a,b,G,n,h)$ in the binary case) must be agreed upon. Also, each party must have a key pair suitable for elliptic curve cryptography, consisting of a private key d (a randomly selected integer in the interval $[1,n − 1]$) and a public key $Q$ (where $Q = dG$). Let Alice's key pair be $(d_A,Q_A)$ and Bob's key pair be $(d_B,Q_B)$. Each party must have the other party's public key (an exchange must occur).
Alice computes $(x_k,y_k) = d_AQ_B$. Bob computes $k = d_BQ_A$. The shared key is $x_k$ (the $x$ coordinate of the point).
The number calculated by both parties is equal, because $d_AQ_B = d_Ad_BG = d_Bd_AG = d_BQ_A$.
The protocol is secure because nothing is disclosed (except for the public keys, which are not secret), and no party can derive the private key of the other unless it can solve the Elliptic Curve Discrete Logarithm Problem.