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.
These two might be helpful (if just for an indication):