Time machine will not be able to work with most Externals you purchase unless there mac compatible and if so, they will be in Fat32 which can only store up to a 4gb file. So you need to format your drive and change the mapping to the Native format of OSX
You want to use Disk Utility to perform this function.
Click on the new external drive in the left pane of Disk Utility.
Then you should first partition the new drive by clicking on the partition tab, making sure to use the GUID partition table if you plan on using this drive exclusively for MAC and if you ever may want to boot from this drive. (I have my external partitioned so that 1 partition is for Time Machine and the other is a bootable partition which can be useful for troubleshooting)
Once you have partitioned the drive you can click on the erase tab, select MAC OS extended (journaled) as your format then click on erase near the bottom right.
Once this is complete your drive is good to go!