How secure do you want to be? To do a forensic delete, you need to go through a full format something like 7 times (data can be recovered from a HD even after its been formatted). If you're just wanting to remove all old data before starting over, just redo your partition table. You can use fdisk, or go through the automated process during install - erase the old partitions and you're done.
Good filesystems are ext3, ReiserFS, and XFS.
ext3 is probably the most widely used and perfectly acceptable for anything you might want to throw at it as an average user.
ReiserFS is good when you have a LOT of very small files. It's a btree file system so searches are generally very fast (hence being good for LOTS of really small files). Supposedly it has as good of performance as ext3 when you have a normal number of files in each dir - not a bad choice.
XFS has some great fault tollerence... that's about all I know about it. I seem to remeber there something about it that I didn't like (and therefore have never used) , but I can't, for the life of me, remeber what that was. Maybe I just liked reiser better.
Anyway, those are the three biggies - go do research on them to see what best suites your needs. Either Reiser or ext3 should be perfectly fine for anything you'd want to do with it.