How should I format my hard drive for use on both a Mac and a PC? Is there any way I can also use Time Machine with this drive?
Format HFS+, use as time machine. On your Windows system, install non-free MacDrive and you can read it. http://www.mediafour.com/products/macdrive/
We do this here for some of the drives that arrive to us from external vendors that are all in HFS format (and some windows people need to read it).
Or, you can just share it from your Mac over your home LAN (not exactly that useful, but..)
I use NTFS-3G for the Mac and formatted the drive NTFS. This allows me to use it on both Windows and Mac and easily move between these machines.
You can use FAT32 but it does have a file size limitation of just under 4GB (232−1 bytes).
Formatting as FAT32 will let both your PC and your Mac read from and write to the disk. If you plan to directly connect the disk to your Mac, Time Machine will only work on it if it's formatted as an HFS+ volume (which Windows can't read without installing some third-party HFS+ driver software).
If the drive is big enough, consider breaking it into two partitions. The first partition as FAT32/NTFS (use the NTFS-3G driver) and the second partition as HFS+ for use with Time Machine.
Pitfall is that you have to decide how big you want each partition to be and it's a bit of a pain (though not impossible) to change once set. Though at least if you chose NTFS you could keep a copy of the driver on the HFS+ partition so you could use it with any mac.