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). Both the subversion sources and the source distribution ship with an adapted version of Pyrex, so you do not need Pyrex installed.
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.