I have been running PPC Linux on my Power Mac 9500 for a while and it has been pretty trouble free. The only real problem I ran into was formatting the disks.
I would recommend ordering the CDs from PPLinux.org rather than downloading the HFS versions and burning them to CD. I tried multiple times using Resedit to make the CDs bootable, even using the specific version of Adaptec Toast that they recommended, but it never worked out. Unless you want to make a dual boot between the MacOS and PPC Linux, I recommend paying the 40$ for the CDs.
You could also look into Yellow Dog Linux. I don't know anything about it, other than it is very popular as a server.
I don't hear anything about MKLinux. I fear it might have disappeared..?