Removing and creating a partition
Having decided your drive's name (let's call it sda) we must now remove the default partition that the manafacturer put there:
sudo fdisk /dev/sda
This will start fdisk. We want to remove the partion(s), there should only be one.
It might ask you for the partition number, press 1 and enter. If there are more then delete them too.
Now to make a new partition.
This will make a new partition that uses the entire disk. If you want more complex partitioning then read the fdisk manual (man fdisk) or use parted or some other app.
Here's what we did with n, the values will differ from yours:
Command (m for help): n
p primary partition (1-4)
Partition number (1-4): 1
First cylinder (197-621, default 197):
Using default value 197
Last cylinder or +size or +sizeM or +sizeK (197-621, default 621): +128M
Now to write the new partion and exit, press w and enter.
You should be ready to make a filesystem now.
Making a filesystem : "Formatting"
You need to put a system in-place, on the disk, such that it can handle files. This is called (unsurprisingly) a filesystem.
The one we are going to use is called "ext3". On Gnu/Linux we are spoiled for choice and there are loads of filesystems you can use, go do some research if you want to.
So, let's make the filesystem:sudo mkfs.ext3 /dev/sda1
* Note the 1 at the end, because we are making the filesystem in that partition (thanks Mike)
Now it will go off and do strange stuff, simply wait for it to finish.
Using the new file system
Well, at this point you should be able to right-click on the icon (on your Desktop) and choose "mount" (I assume that's the verb it will present to you). After that you should be able to open a window and use the drive*
* all this assumes it's an external USB drive.
If you cannot then you will need to mount it yourself, try:
sudo mkdir /media/sda1
sudo mount /dev/sda1 /media/sda1
Note: We are actually mounting the first partition on the drive, hence the 1 at the end: sda1
And the mounted directory can be anywhere you like, but its common location is /media.