I wasn't 100% sure you have a matx board, but you can check, if you have 4 expansion slots(or sometimes 3), then it likely is matx, but if you have 6-7, then it's atx.
Matx will fit in either atx or micro atx cases, so it's a "safe bet" unless emachine used a "proprietary" motherboard, that isn't a normal format.
Amds are faster than intels for games(generally, of comparable speed cpus), but to get a amd cpu, you'll need a amd cpu and an amd compatible motherboard. That means you'll spend at least $160(the cost of an athlon 64 3200+ 939) more than if you'd reuse your current cpu. A celeron isn't a very fast cpu, and not the best for games though.
A graphics card can make a huge difference. The integrated intel graphics the emachine has are some of the slowest graphics around, most recent add in graphics cards are much faster. Do you know what graphics card you have, and what slot type it uses (agp, pci, pci-e)?
If you need any help when you do this, I'd be glad to answer your questions. You probably will need some thermal grease to put on the cpu, because when you remove it from the current board, it will break the interface between the cpu and the heatsink. Artic silver 5 is good grease. Be sure to clean the cpu and heatsink good with rubbing alcohol on a piece of material before applying the new grease, and don't use much grease, like a grain of rice sized amount.
If you would want a new amd motherboard and cpu, you could get something like this.
Board
http://www.newegg.com/Product/Product.asp?Item=N82E16813138264
Cpu
http://www.newegg.com/Product/Product.asp?Item=N82E16819103535
It also has built in graphics, but has a pci express x16 slot instead of an agp slot like the board that would work with your current cpu(celeron). Pci-express is newer than agp.