If you are using Time Machine, simply format to HFS + Journaled and let Time Machine do it all. If you are making a clone that will be backed up by another software program, format and clone.
What you do depends upon what you want it to do.
I have a Time Machine external drive, and a cloned backup of my boot drive. So you can do both, just not on the same drive.
I just purchased a new hard drive to use in a Mercury Elite Pro enclosure for my backups.
My question is should I format the new drive and clone it first, or should I format and then backup using Time Machine?
OS 10.5.8, G5 Dual

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic