I have installed Linux on an HP iPAQ hx4700 PDA (624MHz XScale PXA270, 64Mb RAM, 128Mb flash, 480x640 screen).
As others have pointed out the main problems are finding (1) a boot loader and (2) drivers for your device. In the case of the hx4700 these problems were already solved for Familiar Linux (familiar.handhelds.org); SDG Systems produced a boot loader and others produced the kernel patches and drivers.
A more generic boot loader is HaRET (Handheld Reverse Engineering Tool), a Linux bootloader which works from the Windows CE environment. I haven't used it myself because I wiped WinCE off my iPAQ years ago.
Drivers and platforms for ARM devices are being developed for the Linux kernel all the time; check out the source code under ./arch/arm. But you may not find exactly the right combination for your device. Being a kernel hacker helps!
As for a Linux distro, I first used Familiar Linux. But that is no longer actively developed. So I switched to Angstrom Linux (www.angstrom-distribution.org). But that doesn't offer the latest version of the Mozilla Fennec browser. And in both cases I found the desktop environment (e.g. GPE) to be too resource hungry.
So I have now rolled my own distro from the latest software sources. In particular I am using a window manager called PAWM (Puto Amo Window Manager), which is small and perfect for a device without a keyboard, and fennec-2.0a1pre built from bleeding edge sources. Yes, they do actually work in 64Mb of RAM! It does take some effort to port, configure, debug and fix the software, but it's fun to do.