Invented by Edward Craven Walker, an ex-RAF pilot in 1963, who based it on an egg timer he saw in a country pub ten years previously (apparently created by one "Mr. Dunnett"). The lamp works due to the behaviour of the two materials in the bottle when heated. For the lamp to work correctly the substances used must be:

a) very close to one another in density, and
b) immiscible

The original lava lamp consisted of a mixture of water, wax and a "secret ingredient" , according to the original patent (US Patent # 3,570,156 March 16, 1971) this was "a mineral oil such as Ondina 17 (R.T.M.) with a light paraffin, carbon tetrachloride, a dye and paraffin wax". This substance is then placed in a 70/30% (by volume) mixture of water and a liquid which will raise the coefficient of cubic thermal expansion, and generally make the whole thing work better. The patent recommends propylene glycol for this

Technical information taken from:
www.mathmos.com
www.howstuffworks.com
http://www.uspto.gov/patft/