I think the original paper is very readable: ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf