Upgrading the mobo on a pre-assembled PC is very difficult, because they often use unconventional designs. So you're not likely to find a new motherboard that will fit in your case. Solution: buy a new case.
You want to upgrade the mobo, processor, RAM, and video card. Note that these are the 4 generally most expensive components.
You'll need a new case in order to use a standard motherboard.
There's a good chance you'll need a new PSU to power your improved hardware, as most pre-assembled PCs come with PSUs that have just enough wattage to power the stock hardware and not much to spare. Upgrading to a modern Core 2 or Socket AM2 processor alone will require a lot more wattage considering how much has changed with processors since the days when the P4 was the standard. Throw in a medium or high-performance PCI-E graphics card and it's almost certain your current PSU doesn't have enough wattage to cover everything.
So let's recap. The parts you'll need to purchase include: processor, mobo, RAM, video card, case, and power supply.
Sounds like a complete system upgrade to me. The only things left that you really want to keep are the optical drives and hard drive(s), and you can always keep the old RAM as well just for the sake of having more (unless you're going to buy enough new RAM to fill all of your new mobo's slots, which you probably won't). These should be easy as even pre-assembled PCs normally conform to industry standards with these components.