The most important rule of data recovery is do nothing that can change the data you have Creating a partition table is a bad idea, and fdisk and gparted are partition editors. They change the data and as such they risk destroying the data
I think we need to start with what actually happened to the data. If it was overwritten, it is very likely you are out of luck - modern drives are tightly packed enough that a simple one pass wipe irrecoverably deletes data.
If its a logic board failure, or some other low level failure, you will need a professional to swap parts and get it to work. You don't have the parts or the expertise. They might also have other tools at their disposal.
Lets assume you have the best case scenario - that just your partition table is malfed up.
Backup with a tool designed for recovery - I favour gddrescue. Then make a copy of your backup. Work off this copy. In this specific case testdisk should do the trick - you're working off an image so if something went wrong, all you did is munge up a copy of a copy of the data. Try other tools (kpartx works well for tools without native image support on linux) . DO NOT EVER WORK ON THE DRIVE YOU ARE TRYING TO RECOVER DIRECTLY
If all this seems alien, do as Tom O'Connor did and hire a professional or better yet, restore from the backups you should have been making.
3It's hard to answer your question without knowing how you lost that data... did you rm it? delete the partition? fill your /dev/sdb with zeroes? drop the harddisk out of the 30th floor? – replay – 2013-08-30T10:05:25.930