You need Python 2.3 or later.
You need libxml2 and libxslt, in particular:
libxml 2.6.20 or later. It can be found here: http://xmlsoft.org/downloads.html
If you want to use XPath, do not use libxml2 2.6.27.
libxslt 1.1.15 or later. It can be found here: http://xmlsoft.org/XSLT/downloads.html
Newer versions generally contain less bugs and are therefore recommended. The HTML parser benefits from libxml2 version 2.6.21 or later, which support parsing horribly broken HTML. XML Schema support is also still worked on in libxml2, so newer versions will give you better complience with the W3C spec.
If you have easy_install, you can run the following as super-user (or administrator):
easy_install lxml
This has been reported to work on Linux, MacOS-X 10.4 and Windows, as long as libxml2 and libxslt are properly installed (including development packages, i.e. header files, etc.).
If you want to build lxml from SVN you should read how to build lxml from source (or the file build.txt in the doc directory of the source tree). Building from Subversion sources or from modified distribution sources requires Cython to translate the lxml sources into C code. The source distribution ships with pre-generated C source files, so you do not need Cython installed to build from release sources.
If you have read these instructions and still cannot manage to install lxml, you can check the archives of the mailing list to see if your problem is known or otherwise send a mail to the list.
For MS Windows, the binary egg distribution of lxml is statically built against the libraries, i.e. it already includes them. There is no need to install the external libraries if you use an official lxml build from cheeseshop.
If you want to upgrade the libraries and/or compile lxml from sources, you should install a binary distribution of libxml2 and libxslt. You need both libxml2 and libxslt, as well as iconv and zlib.
On MacOS-X 10.4, you can try to use the installed system libraries when you build lxml yourself. However, the library versions on this system are older than the required versions, so you may encounter certain differences in behaviour or even crashes. A number of users reported success with updated libraries (e.g. using fink), but needed to set the environment variable DYLD_LIBRARY_PATH to the directory where fink keeps the libraries.
A MacPort of lxml is available. Try port install py25-lxml.