Vicki the only thing I could find said Apple did not intend for that fan to be user replaceable suggesting you replace the case. However I read where some have replaced it so my suggestion is as follows. Mind you I have not done this but its how I would go about it.
1. Remove the optical drive--easy.
2. Remove the hard drive--easy
With those items out of the way you have more room to look and see if you can remove the fan. If you succeed please leave a write-up to help future owners. Link provided on removals--good luck.
Power Mac G5 Repair
I just opened up my G5 and looked at the setup for the fan. With hard drive removed it appears to have rubber pins holding the fan in place. I don't know if you can remove them without breaking them so I would have replacements on hand before starting. Also I cannot see how the power is hooked to the fan but since you have a new fan you should be able to figure it out. Once again good luck.
Looked at a replacement fan on ebay and the appears to have a molex connector so with care you should be able to switch the fan out.