At least 4MB, and then you will need to use special installation procedures until the disk swap space is installed. Linux will run comfortably in 4MB of RAM, although running GUI apps is impractically slow because they need to swap out to disk.
Some applications, like StarOffice, require 32 MB of physical memory, and compiling C++ code can easily consume over 100 MB of combined physical and virtual memory.
There is a distribution, "Small Linux," that will run on machines with 2MB of RAM. Refer to the answer to: "Where Are the Linux FTP Archives?"
A number of people have asked how to address more than 64 MB of memory, which is the default upper limit in most standard kernels. Either type, at the BOOT lilo: prompt:
Or place the following in your /etc/lilo.conf file:
The parameter "XXM" is the amount of memory, specified as megabytes; for example, "128M."
If an "append=" directive with other configuration options already exists in /etc/lilo.conf, then add the mem= directive to the end of the existing argument, and separated from the previous arguments by a space; e.g.:
# Example only; do not use.
append="parport=0x3bc,none serial=0x3f8,4 mem=XXM"
Be sure to run the "lilo" command to install the new configuration.
If Linux still doesn't recognize the extra memory, the kernel may need additional configuration. Refer to the /usr/src/linux/Documentation/memory.txt file in the kernel source as a start.
For further information about LILO, refer to the manual pages for lilo and lilo.conf, the documentation in /usr/doc/lilo, and the answer for: "Boot-Time Configuration.", below.