A 350 Watt is enough if it has 22A on the 12V rail. The ATI 9800 requires less power than the GeForce 8600. Also Emachines says it is upgradeable to PIC-E, because there is a PCI-E slot. Not all cards need that much power, so the PSU can handle it, thus it is upgradeable to PCI-E.
Also since it needs 350 Watts try and get one that has 450+ watts, if your current one isn't enough. I say 450+ because you also have other parts that need power (ex. Motherboard, CD-Rom, HDD).
EDIT: Your computer should run the 8600 with your PSU but it will be at limited power and will strain other parts. It is a bad idea to run it for more than a few days like that. If the PC fails to start you will know the PSU is insufficient.