I don't pretend to be an expert, so I hope I don't get shot down for this :-/
You're almost right with fdisk - type just
> fdisk /dev/hda
> fdisk /dev/hda1
since you partition a hard drive, not a partition. There's a help menu once you're in.
To format the partition, quit fdisk (saving changes if required), and use mkfs. Running mkfs.reiserfs should format a partition as reiser, mkfs.msdos as FAT, mk.ext2 etc.... Make sure partition type and format type match - although it should complain if they don't. My distro has these tools (SuSE) - not sure about RedHat...
You can now add the partition to fstab and mount as usual.
Hope that's of some help - let me know how you get on and if any of that's not correct?