cpu - all the AMD Athlons in my house work great. Would recommend. (I got 'AMD Athlon XP 1800 +' and other computer has '1700 +' and from all accounts the 64 bit AMDs work fine).
graphics card - nvidia, anything you can afford really. They provide free drivers.
Memory shouldn't matter, my ASUS MB works great.
I don't have much experience with hardware and linux, but i think there is a linux hardware compatability website somewhere, its a little outdated but should provide an indication.
Edit: These two might be helpful (if just for an indication):
-
https://hardware.redhat.com/hwcert/index.cgi
-
http://www.linux-mandrake.com/en/fhard.php3
