How do I create new partitions and format my hard drive in parted?

First, make sure you understand the difference between primary, extended and logical partitions. To create a logical partition, you first need to create the extended partition that will contain it. If there's only one partition on a drive, there's no point in not making it primary. Below I'll give instructions for a logical partition; creating a primary partition is similar, only simpler, so you should be able to figure it out.

Parted isn't the easiest tool for a straightforward task, a dedicated partitioning tool such as cfdisk or even fdisk may be easier to apprehend. But here goes (untested, make sure you understand what's going on and don't proceed blindly if you see error messages). You'll need to enter the size of the device when creating the partition (parted displays it).

/dev/sdb
mklabel msdos
mkpart extended 0 123456
mkpart logical 0 123455

Then run mkfs.ext3 /dev/sdb5 outside Parted.

If you choose to use cfdisk, you should be able to navigate its menu-driven interface. If you prefer fdisk, the sequence of instructions is:

n             create partition
e             extended
1             number (1–4)
<return>      accept default start
<return>      accept default end
n             create partition
l             logical
<return>      accept default start
<return>      accept default end
p             show the current table, review it
w             write changes
q             exit