First you can upgrade to almost any size (GB/TB) HD that is 2.5" and only 9.5mm high. So your options here on what to get is not limited to a 500GB drive. With that said you do have one issue you must watch out for as your system uses the older SATA I (1.5 Gb/s) interface. You must make sure what ever drive you get can run at this lower I/O speed. Many HD's today are SATA III (6.0 Gb/s) or SATA II (3.0 Gb/s).
If you really want some zip I would recommend a hybrid HD (typical HD with a SSD cache). These drives are called SSHD. Seagate makes one that should work for you as it has SATA I/O speed auto sense. But you do need to make sure the EFI firmware is up to date. Before doing anything follow this Apple TN on updating EFI & SMC firmware updates for Intel-based Macs. And follow this IFIXIT guide on how to replace your HD MacBook Core 2 Duo Hard Drive Replacement. Here's a vid on the process Apple MacBook Hard Drive Install
OK lets review the needed steps to save your current data and transferring it over to your new HD:
First you should get an external USB HD so you can backup your drive as an option you could also get an external case to house your current HD in (more on this later).
If you are using an older version of OS-X you may want to think about upgrading to the newest version your system can support. One issue here is the amount of RAM needed and also the versions of your current Apps. If you are still running any OS-9 apps then you will need to stay with OS-X 10.5.x (Leopard). If you are thinking about going to Lion You will need to up the RAM to a minimum of 2GB (I strongly recommend going to at least 4 GB) the max is 6 GB using one 2 GB and one 4 GB memory module. Also note you can't run any higher OS-X as you are limited to 32bit mode on this system and when you do buy apps you do need to make sure you get 32bit or 32/64bit combo apps. Be careful with updates as sometimes they are only 64bit versions now.
I do recommend first upgrading your RAM and the OS as the first step if you haven't done this yet.
OK, now the easy part ;-}
Once your system is stable with the new RAM & OS make a fresh backup onto your external HD. At this point you will need to have your new HD in hand and you will need a means to connect your new drive to your system.
If you have access to a second Mac system this could be faster as you could use a FireWire case to temporally hold your new HD and connect it to the other Mac (if it has a FireWire port) then using this system directly (or into Target Mode and then via a Ethernet connection to your system) prep and install a fresh copy of OS onto your new HD. Depending on what your second Mac is and the OS it has you might find this a bit quicker. Otherwise you will need to use the USB port to connect via the universal adapter cable (SATA to USB) for your system as your system has slow USB ports this will take a bit of time. You also will need to supply power for your HD externally as your system USB port can't support the load of the HD (more so when prepping it as well as installing OS or other software).
Prepping your new HD:
Yes you do need to partition & format it using Apples Disk Utility you will partition the drive (one or two partitions being ideal). Then you will need to format the partition(s). Here's a good writeup on the steps How to Partition Your Hard Drive on Mac OS X Snow Leopard. Don't let the OS version listed here worry you its the same steps in all of the versions of OS-X. WARNING! Make sure you don't alter your current HD settings! Next you will use the OS installer app (or OS DVD) to install the OS onto your new HD. Once you have the OS installed you should try it out. To do that go into the control panel and select it as the boot disk and restart your system if all goes well your new HD should be the first listed drive. As you are loading though USB it will take a bit of time to come up, get a cup of coffee and mellow out a bit. As your halfway through!
If you remember at the top I stated you could do without the backup HD (cheapest option). Here you will use your current HD as the backup. This is were you use an external USB case to house the new HD to prep it and then after you install your new HD you put you old HD into this case.
OK last software step - Moving your files over:
At this point your new HD is prepped and a fresh copy of OS is on it. Your next step is either migration or cloning. Migration uses Apple Migration assistant (the preferred way) and Cloning uses an app to replicate between the two HD's. The only wrinkle here is cloning requires a third drive as the boot disk and location where the cloning app is located as you can't have any files open on either disk you are cloning. Migration requires a second Mac to host the drive Heres a good writeup How to use Migration Assistant to transfer files from another Mac Here you will take your old HD out and place your new HD in the system. Then follow the section: Time Machine or other disk Your old HD is connected on the other Mac in Target mode in either a USB or FireWire case (FYI: Some cases offer both ports!) Then in section 7 select your old HD as the source from the other Mac.
Pro's 'n' Con's - Migration needs two systems but you end up with a fresh OS install. Cloning cares over all of the old system files over and you need a third disk as the boot drive. This could be a USB thumb drive.
Hopefully that answers most of your questions. I know its a lot here to read, doing it is much easier. Good Luck!