Is it possible to run Linux on a PowerMac G4? If so, how do I install it?
One option is the PowerPC build of Ubuntu:
Another popular option is Yellow Dog Linux:
My recent (2011-10+) experience...
I fought with Ubuntu 10.04 LTS PPC port trying to get it onto my PowerMac dual G5 (2003) for quite a while. No luck with the Desktop nor Server install CDs, I did manage to get the "Alternate" install CD working -- but it took 3 tries before I managed to not mangle the yaboot bootloader install & config -- not very fun.
I had much better luck with http://MintPPC.org -- it is a PowerPC only distro, based on the Very stable and well-supported Debian distro. It supports even ancient G3 machines, so your G4 should be no problem. The community there is responsive, helpful and mostly former Mac-heads. IMHO that is a big benefit over generic Linux distros (Fedora, Ubuntu, etc) which tend to consider old PPC hardware as an unpopular afterthought.
I have yet to try http://YellowDogLinux.com They are also purely a Mac / PPC heads, which is good for newbie support, but the most recent ISO image is from July 2009-06-29.
As for this install process itself:
Good luck & happy hacking, ./ddd